Hinduism: Research Meditation before the Indian spawn.
Buddhism: Build a (Hindu) temple. Easiest by far.
Zoroastrianism: Research Monotheism before the Persian spawn. Easier said than done (see below).
Confucianism: The first real struggle. I had to whip the Oracle out of Niwt-Rst in order to barely secure myself Mathematics, which ended up being one turn before the Chinese got it. What made this difficult is that neglecting Monotheism in favour of Mathematics would result in me not be able to outpace Persia. At least two dozen reloads were spent meticulously planning this.
Taoism: Simple. Just get Calendar, before or after Theology. China's AI at the time didn't seem to try very hard for this, probably because it assumes that the other ancient and classical civs won't have the most expensive prerequisite tech (Mathematics, of course, which it very clearly prioritises). I could have just been lucky, but in all of my reloads Taoism was never stolen from me.
Catholicism: Randomly got much harder after a certain necessary reload during my long battle for Islam, with Rome stealing it as early as 250 BC. Beeline. I couldn't have gotten to Theology in time without some very, very fortunate trades with Phoenicia. I think they may have been the only civilisation willing to trade with me for the whole game.
Islam: The second great struggle. Getting Divine Right before the Arab spawn is very, very hard when you only have one city and are constantly being attacked by angry Nubians who apparently live in northern Egypt. It took dozens of reloads due to my population being hampered by a random plague. There's nothing special to be said here; the entire battle for Islam was spent maximising my research output while painstakingly reloading to combat Egypt's many, many barbarian threats. As you can probably guess, building a military wasn't exactly my priority during this game.
Orthodoxy: Arguably the hardest of all the religions to found intentionally: building the Apostolic Palace is required to keep the Catholic holy city, but it's also intended to trigger Orthodoxy's foundation in a separate nation. Fortunately, there was no Byzantium when I did this, but my Ethiopian friends to the south and the Russians way up north both had the ability to steal Orthodoxy. Honestly, I'm not sure how I ultimately did it, but it did involve purposely conquering Ethiopia just to eliminate them from the game, and then throwing Aksum to the Independents. (I seem to recall keeping Aksum, once, and then founding Orthodoxy -- and, to my abject horror, watching it be founded there, instead.) Many times did Russia get it, but after enough reloads, eventually the white cross appeared over Niwt-Rst.
Note: I did actually get Orthodoxy much earlier, before the Russian spawn and by removing Ethiopia (making me the only candidate), but this process ended up costing me too much time to get Divine Right.
Protestantism: For a finale, this was actually a complete pushover. With nothing else to worry about, I beelined for the Printing Press and thereby completed the challenge in 1420 AD.