The problem is much more acute if you assume that God, or other such all-powerful being, doesn’t exist. In this case he can’t make the rock, isn’t around to lift it and thus, logically, the only way you can answer the question is if God exists in the first place. Besides it’s more fun with omipotent beings around.
I would be much more worried if God stoped believeing in us, then where would we be? 
I don’t know, Ramanujan. It seems to me that there is the possibility of The Rules™ being made by God (as he would be the first cause, say), and yet also being subject to them. It is no less paradoxical than a rock so heavy.
I’ve always looked at the “rock so heavy” like this: Can god etc? Yes ::poof:: ((rock appears)). “Ha! But if it is so heavy he can’t lift it, then he clearly isn’t all-powerful!” ::God lifts rock:: “But that means he can’t be all pwerful, since he didn’t make the rock demanded of him.” ::poof:: ((another rock appears)) etc ad nauseum.
I mean, why couldn’t God be bound by his own rules? If he made them, are they higher than him or not?