A The pre-existence of the soul is a cornerstone of all ideas of reincarnation, so all religions that espouse reincarnation believe in it, such as Hinduism, Buddhism, etc.
Some religions teach pre-existence but not reincanation. That includes Zoroastrianism, some sects of Judaism, especially those that accept the apocrypha and pseudepigrapha. For example, in The Book of Wisdom it says:
As a child I was naturally gifted, and a good soul fell to my lot; or
rather, being good, I entered an undefiled body. (Wisdom 8:19,20 NRSV)
The Books of Esdras and Enoch are similarly cited, for example, by Mormons.
The Greek Philosopher Plato taught the idea of the pre-existence of the soul. Some scholars believe this idea influenced later Jewish beliefs, such as the Medieval kabbalists. See: The idea that the soul is the human instrument of spirituality became more prominent over the course of Jewish history.
The only thing that all Christians would agree on is the pre-existence of Jesus' soul. This article gives a summary for many denominations: Compare Religions: Pre-Mortal Existence of Man
These denominations affirm belief in pre-existence:
- Christian Science
- Church of Jesus Christ of Latter Day Saints (Mormons)
These denominations have no formal statement and leave it up to the individual:
- Disciple of Christ
- Presbyterian
- Quakers
- United Church of Christ
Some Early church fathers believed in the pre-existence of souls, such as Origen of Alexandria, a neo-platonist. For additional discussion of that topic, see: Did any other early church fathers besides Origen teach the pre-existence of souls?