In
The Letters of J. R. R. Tolkien, Letter 153 (To Peter Hastings (draft)) includes a footnote that gives a pretty good overview of religion in Middle-earth:
*There are no temples or 'churches' or fanes in this 'world' among 'good' peoples. They had little or no 'religion' in the sense of worship. For help they may call on a Vala (as Elbereth), as a Catholic might on a Saint, though no doubt knowing in theory as well as he that the power of a Vala was limited and derivative. But this is a 'primitive age'; and these folk may be said to view the Valar as children view their parents or immediate adult superiors, and though they know they are subjects of the King he does not live in their country nor have there any dwelling. I do not think the Hobbits practiced any form of worship or prayer (unless through exceptional contact with Elves). The Númenóreans (and others of that branch of Humanity, that fought against Morgoth, even if they elected to remain in Middle-earth and did not go to Númenor; such as the Rohirrim) were pure monotheists. But there was no temple in Númenor (until Sauron introduced the cult of Morgoth). The top of the Mountain, the Meneltarma or Pillar of Heaven, was dedicated to Eru, the One, and there at any time privately, and at certain times publicly, God was invoked, praised, and adored; an imitation of the Valar and the Mountain of Aman. But Númenor fell and was destroyed and the Mountain engulfed, and there was no substitute. Among the exiles, remnants of the Faithful who had not adopted the false religion nor taken part in the rebellion, religion as divine worship (though perhaps not as philosophy and metaphysics) seems to have played a small part; though a glimpse of it is caught in Faramir's remark on 'grace at meat', Vol. II p. 285.
This doesn't address the beliefs of the Dwarves; however we know that Durin's Folk revere the Vala Aulë (as Mahal) and believe in a form of reincarnation concerning Durin the Deathless, the father of their House. They might have developed a more formal form of religion as compared to the Elves and the Dúnedain.
The Avari Elves would at least have knowledge of the Valar and Eru, although their attitudes toward them might differ from those of the Elves who took part in the Great Journey. Having never dwelled in Valinor, the Avari might tend to remain in Middle-earth after their physical death rather than moving on to the Halls of Mandos.
Orcs might have developed numerous belief-systems and lesser cults during the long years when Sauron was absent or inactive, although the cult of Morgoth would still have dominated. Beast-cults and ancestor worship might have arisen at those times. The Goblins of Moria, for instance, might have deified the Balrog to some degree.
The Men who did not belong to the Three Houses of the Edain. probably held many different religious beliefs as they had little or no knowledge of either the Valar or Eru. Those that were the most firmly under Sauron's control were encouraged or forced to belong to cults of Morgoth. Beast-cults might have also flourished; I have already speculated about dragon-cults arising in the East. Shamanistic beliefs might have been founded upon the very real existence of Ainur and other nature-spirits, sometimes incarnated in physical form. In the most well-developed of the pagan lands the native beliefs might have become more formalized and ritualized. There are early, real-world civilizations that go back to the time of Tolkien's Middle-earth (such as the Sumer civilization in southern Mesopotamia). You might borrow from them.
