Back in 2e, Clerics were permitted a 'change of heart' exactly once with no adverse, long-term penalties.
If you'd like to add some flavor (and it's in the player's interest), require of him an Atonement spell from a high-ranking cleric of his new Deity. Maybe he has to donate to the church and/or perform a great service to earn it. Maybe such a service might include founding a new church/abbey/shrine/sacred space in or near a settlement.
The official D&D Adventurer's League allows a near-total 'reroll' of a character up to level 5. If your player doesn't want to be a CLERIC anymore, I'd suggest he be allowed to multi-class. If he wants to stay the same person AND be a new class, it's all in your hands, but better to let him play the character he wants.