For a recent one-shot, the plot ended up demanding godless clerics... The gods themselves had been essentially negated, and had no literal involvement in the world (BTW, it wasn't another free-the-gods or stop-the-evil-people-from-freeing-the-gods scenario... it was just a side-effect). People still worshiped gods and got spells, but these spells were not actually granted by the gods, just a side-effect of the worship... Tapping into Divine Energies or what have you.
I ruled that clerics could just grab any two domains, and come up with a god of their own (characters didn't have backgrounds -- specifically couldn't, again, part of the plot) to worship. While in principle this made sense to me, in practice it caused some problems of its own.
While I have no objection to godless clerics with regard to versimilitude, they do seem to create some role-playing problems... First, picking any two domains tends to lead to min-maxing, and while you can still do this to a certain degree with standard gods, you still end up being tied to that religion, and having these tenets to follow. From my own experience as a player, this is a good thing -- keeps the character interesting, gives me material to work with in terms of personality. Once you reduce it to domains, it just gets nebulous -- here's this devoted, faithful character, but you're really not sure as to what... Makes it harder to roleplay, which cuts a big limb off the game.
So while I'd still allow godless clerics in the future, I'd still require a very clear idea of what principles they're worshiping, and what ideals they have to go along with it.