A really good real world example of a paladin who attains powers by calling rather than training is Joan of Arc, but her power still comes from her faith in the Catholic god (PLEASE do not make this political by honing in on the Catholic thing, it's just what she was).
Carrying this over in to D&D as an analogy, even if a Paladin character were to be created without a deity, the power of the Paladin's skills still comes from /some/ deity, and a Paladin can't draw on power without invoking that deity, so I just don't see how a Paladin can be godless.
I don't think the discussion has anything to do with "denying the option" but trying to work out a plausible way that it fits within the setting. As it stands, in the Forgotten Realms, even post Sundering, Paladins have deities, so their absence in this game does seem jarring to some, and there are mechanical considerations to take in to effect unless you're willing to just say "because you can" which is effective, but unsatisfying as a reason.
