Obviously, you need to talk to him like an adult and see what he wants to do. That being said, some classes fit better for a Paladin without Paladin powers than others. The most obvious choice is Fighter, because it shares most of the same proficiencies, fighting styles, and powers, with some mundane powers of its own. There are other options, however, with varying levels of work on your end. However, the work can be very rewarding. Personally, I would lean heavily on a homebrew solution.
I regularly homebrew just about everything. For example, in the last year, I had a PC warlock sell their soul to several different demons. In times of severe trouble, she could pull a Shonin Anime trope and call upon the demon for superpowers (immunity to non-magical weapons and a bunch of resists, bonus damage, flight, etc.), but her body would be twisted by the demon and there was a chance that the demon would take over entirely. She started getting powers at Level 3 (5e DnD) and even changed her race. Her demons got jealous of each other, impacting on her class abilities. Part of the journey was figuring out how many demons were possessing her, and how many were a figment of her imagination (insanity is a possible side effect of overuse of the demon's powers).
Basically, I suggest using this as an opportunity to introduce interesting mechanics and role-play opportunities.
Option 1: You're a Fighter, Harry
We have a class that's a catch-all for a fighting person - the Fighter. If a fallen Paladin doesn't go Oathbreaker, you might want to transition them to straight Fighter 6. This would give them Action Surge, Second Wind, a Feat, and access to a fighter subclass. I would suggest a non-supernatural subclass as that would be easier to explain. Ask him and see what he wants to do.
Option 2: Transition
Another option that might be less jarring is to make him a fighter (or another class), but give him access to his class features over several levels. This will likely make him a bit weaker than he would otherwise be, which may make him feel like his character sucks. Give him something in-character to make up for it (a cool ability, a title, a magic item - make it interesting) and make him feel special.
Maybe he let a demon or spirit into his soul, and it's eating away at him. Give him some cool powers that he can use when the going gets tough... that he can use at a horrible price. Maybe this is a good time to infect his character with Lycanthropy, or to be chosen as a saint of a god of murderhoboism, or what have you (with corresponding long rest abilities). Go nuts.
Falling shouldn't be a punishment for the Player, it's a punishment for the Character. Use it as a narrative tool intended make his character's journey feel awesome and immersive.
Option 3: Create a Custom Class
A third option would be to keep the Paladin template, but swap out the essential "paladin-y" stuff in conjunction with your player for some homebrew stuff. Maybe he can no longer cast paladin spells, but he can do other stuff instead. This is definitely more work, but can be rewarding under the right circumstances.
Maybe he gets half-caster progression as a Warlock instead of a Paladin? Maybe he can get appropriate daily abilities to fit his character?
It's probably easier to do this as a fighter subclass IMO, but it's definitely an option that would be less jarring than just making him a L6 fighter, subclass and all.