I decided, since this topic keeps coming up, to go back through the edition handbooks I have and actually check Paladin's deity-requiring status. Because I was sure that paladin never actually required a deity, and people were thinking of divine champions, which definitely do require a patron deity.
This is what I found: Paladins have never been required to have a patron deity, going back to 2e. They dedicate themselves to the forces of good and law and divine power is granted via your dedication to these principals (in the same way a druid gets power from dedication to nature, but not worship of gods or spirits). Paladins can be and often are also devout members of their churches, but it isn't specifically their devoutness that gives them powers.
