It depends what you want to do with regard to Clerics and Paladins.
If you're including them as-is, there shouldn't be any issues at all - just have the Cleric select any two domains, and go from there. Done.
If you want to remove those classes as well, then things are a little more tricky. The loss of the Paladin isn't a particularly big deal, but the loss of the Cleric means the loss of much of the party's healing power. Still, that shouldn't be insurmountable - it's no different from a game where none of the players wants to take a Cleric character.
Still, you might want to make sure the PCs have easy access to other forms of healing and/or cut back on the lethality of encounters.
No plans to remove the cleric but need to make them not having a god "make sense"
By giving them access to those domains, how do we explain where that power comes from?
Just a couple of ideas...
The 2nd Edition "Complete Priest's Handbook" included the idea of Priests of a Force or Philosophy. The former should be obvious - they draw power from an element, or storms (rather than the god of storms), or whatever.
The latter is particularly interesting, though - it posits that the Cleric draws power from whatever system of belief he follows. So you could have Stoic Clerics, or Pythagorean Clerics, or whatever.
The one official setting that springs to mind for a "no gods" setting is Dark Sun. There, Clerics draw their power from one of the four elements.
D&D-style fantasy contains a strong assumption of baseline polytheism. If you're going to go with a single god, consider "One god, many saints, avatars, and/or incarnations".
It's just easier that way, and more conducive to entertaining conflict.
I've run campaigns without gods (even without casters) before. It can work out fine.
No Gods
This was a story set at the beginning of the world. People had some suspicions they were put there for a reason, but nobody really knew. The story covered the first gods arising and their conflicts. In the setting the newly risen gods were basically just mid- to high-level characters that could grant spells, eventually including several PCs.
What changed? Divine casters weren't available until people started ascending, but no rules changes other than that.
What challenges did you run into? In theory healing should have been a problem, but wewere used to not having clerics, so it wasn't a big deal.
What objections were encountered? No objections. But nobody is my group back then liked clerics anyway.
What was difficult and what became easier? People dying stayed dead was the main thing. Pacing was no different than any other game without a cleric.
Overall, what were your thoughts? Good campaign. 4/5 stars. Would run again.
If I were to run this again with Pathfinder, I'd probably leave out anything in the "Trained" age category (alchemists, clerics, druids, inquisitors, magi, monks, and wizards) to represent that they just don't exist yet. I could probably pare it down to the "Intuitive" category (barbarians, oracles, rogues, and sorcerers) plus fighters and rangers without any objections from my group.
It'd also be a good excuse to play with the mythic rules. I might actually start with "Children of Myth" rules and work from there, but that's a much more dramatic shift.
No Casters
This worked out... less well. Not for balance reasons or anything, one of my players just really liked casters and I wasn't solid enough as a GM yet to sell it to him or tell him to wait for the next campaign.
What changed? No divine or arcane casters until it's (re)discovered. See: many fantasy novels.
What challenges did you run into? Extremely insistent player.
What objections were encountered? "I only play casters! No wait, I'll play and just complain the whole time."
What was difficult and what became easier? Self-destructed too quickly to say.
Overall, what were your thoughts? Failed experiment. Would have gone better if I had more skill establishing buy-in.
Cheers!
Kinak

(Dungeons & Dragons)
Rulebook featuring "high magic" options, including a host of new spells.