In my post about that southern continent that channels The Lost World pretty strongly in my mind, I say the natives had their gods and those gods helped them fight off The New Empire conquistadors. The question now becomes, are the god gods, or are they just super powerful entities, and does it matter if they are one or the other?
I go back and forth on this topic a lot. I think clerics and stuff screw up a lot about fantasy worlds. How can you have anything remotely resembling widespread starvation or disease anywhere in the world when there are two or three dozen different priesthoods of various bents that can provide meals and healing at a variety of low levels. A 5th level cleric can provide ten gallons of water and a meal that feeds fifteen people for twenty-four hours, and that is with only a 10 in Wisdom, which is highly unlikely. I suppose that relies on a church being fairly helpful in nature, but even "neutral" or "evil" churches could have those services bought by a government in dire straits. I dunno, it just seems to me like healing and such have the potential to muck up anything you try to run. If there does end up being some sort of apocalyptic disease you have to resort to "magic did it" to explain why all the useful cure spells suddenly no longer work.
Sometimes I wonder if the whole "there are no gods and everyone on Hekinoe knows it" thing is influenced more by my personal thoughts and beliefs than by any sort of logic. I don't suppose it matters ultimately. None of my players have voiced any concern over the topic. John seemed to really enjoy playing a Favored Soul way back when, although that was a pretty broken class in my opinion.
Would I ever allow Cleric, Paladins, and the like into my game? No. They're stupid. I remember back in 2nd Edition, the basic Cleric was not allowed to use anything but bludgeoning weapons because they weren't supposed to shed blood. Have you ever seen a crush injury? There is blood, I assure you. Eventually there were rules for customizing your clerics based on their faith, war gods allowed their clerics to use swords and other implements of mayhem. Made more sense, but the bludgeoning thing always struck me as patently ridiculous. Now that I think about it, I think it was based on some Catholic rule or something. Who knows, I'm not a religious scholar and this is all vague recollections. Paladins could only be good guys, because only good religions have soldiers empowered by the divine power of their god. Dumb.
Anyway, I never cared for Clerics in DnD, period. I never really cared for gods either. They were always too invested in the players and the world in general in typical DnD settings. I like Dark Sun and Planescape because the gods were non-existent or the Lady of Pain's bitches. In Forgotten Realms they were a dime a dozen (as common as magic items, which were pretty common in Toril's extremely high fantasy world). They were all over the place, ruling nations, or running around as demigods or souping up various entities serving them to make them chosen. The logic was that gods were dependent on their devotees for power, so they had to be invested in the world and their followers, they couldn't just sit on high and be Cromm-like. They had to wander out of God Town and do shit.
I like the Witch class in Pathfinder, I think it works well in lieu of the whole Cleric thing. You make pacts with various entities and gain supernatural powers from them. Basically amounts to a Cleric with less armor and a weird pet that is an agent of their patron. Besides, devotion and servitude are modeled with role-playing far better than they are with game mechanics.
I lately find myself wondering if I should play a game like "the old gods are returning" or something. Like maybe at the height of their power Kaleshmar decided that they would erase the knowledge of higher powers from the world because if all their Uncout slaves started throwing fireballs and challenging their might, well, it might compromise the stability of the mighty empire. I dunno, like I said, no one has voiced an opinion about the lack of deity-centric fun.