Paladins and Clerics, or other divine casters, have not had to serve a specific deity since at least 3.5 in the generic DnD rules -- a concept or virtue was enough. Forgotten Realms however have had special setting rules that in it you need to be devoted to a deity to gain divine magic.
I'm pretty sure that special setting rule no longer carries weight since they pretty much did made FR the generic standard setting in 5e. But regardless there is nothing new about divine casters being able to cast without following gods.
As for 5e Paladins, I think it is safe to say that as a general rule the divinely associated Paladins are still the most common. But in this edition the power-granting aspect is the oath they've sworn -- possibly to a deity, but not necessarily -- rather than direct worship.
