Haha, that's a good question Kadazzle... my guess is you'd have to wait.
On Noble or Prince, it's definitely very possible, if you start with mysticism, to get an early religion. I used to do that regularly. Since moving up, however, it is usually difficult, unless you have some gems or something, to get one of those two. cronullasharks is completely right, you're usually best served doing something else anyway. Judaism I almost never get... monotheism just isn't as valuable a tech as, say, ironworking, or pottery, or writing.
The later 4 religions are much more possible, and carry a far lower opportunity cost than the early three. I almost never get Islam, just because Divine Right is out of the way and I'm usually pursuing Liberalism. Some spiritual leader tends to get DR much earlier than I ever do.
Others have already mentioned the Oracle>CoL slingshot to get Confucianism. That works, and I would often do it on Monarch, but now that I've moved up to Emperor just getting the Oracle is often difficult, plus you have to be through writing before you finish. I don't do that very often.
The other two religions I found much more frequently than all the rest combined, because they're A) on the way to liberalism, and B) can get lightbulbed by great people. The Great Scientist>Philosophy lightbulb is a HUGE beaker boost for that early stage (1200+!), plus you need it to get to Paper>Education>Liberalism. Usually, however, I have some other religion spread through my lands at this point, so Taoism kind of ends up getting the shaft unless I spread it for happiness/shrine reasons.
So that leaves Christianity, which is a really great one to get. Theology is also on the way up to Liberalism, and I usually get a Great Prophet from Stonehenge (Right there with you thelastone36) to bulb it with. 700+ beakers isn't bad at all for a non-scientist GP. The downside is you have to research Polytheism, Monotheism, and Meditation before you can do the bulb, so sometimes I have him sitting around for a few turns, but it's worthwhile.
The game I'm playing right now, I ended up on a continent with 2 other civs, and none of us founded any religions, so my bulbing of theology ended up being a major money-maker when every city on the continent became Christian. I ended up getting Taoism too by accident, but I haven't spread it much.