You cannot count on it, but with a start with a) mysticism and b) financial leader I founded both of the early religions successfully on monarch (it is probably not a great strategy, but doable). I would always go for Polytheism/Hindu, though, because the AI seems to prioritize the slightly cheaper meditiation, and if you lose the race for Poly, you can try to get monotheism instead.
But usually I (Warlords/Monarch lvl) go for either CoL with the oracle or sometimes Theology and/or Philosophy "bulbed" by a great person, one of those usually works without too much going out of one's way. Of course it all depends how many other civs are there (I usually play standard with 6 or 7? civs) and how many of them are relgious fanatics. The latter seems to be the decisive factor. I have seen Saladin found 4 or even 5 religions in a single game.
And yes, in my experience the step from prince to monarch lvl feels probably steeper than from noble to prince, although you can still play quite sloppy (that's me...) and be successful.