All right, then. Leave for a bit and bind a Succubus. Convince her to seduce him (shouldn't be hard in this case, any demon would jump at the opportunity of corrupting a paladin). Ring of Mind Shielding keeps her safe from his annoying Detect Evil. Introduce them in the next city with the succubus playing the part of a childhood friend of yours. With any luck, a relationship will begin to develop between them. After it goes on a bit, take the Ring back and sit back to watch the show. If he detects that she's evil, then he is suddenly torn. Betrayed is a definite feeling for him. He'll then have to choose what he will do.
1. He smites her as his code of conduct demands, then will probably turn on you in a rage. This is a good thing. Most likely, your other party members will try to stop him. He won't be happy, but now there are three different possibilities:
A. He stops. You get to live, but registering evil (although your other party members won't know). He loses his Paladinship for willingly associating with an evil character (expressly forbidden by the PHB)
B. He dies to the party. Problem solved
C. He attacks your party members. He would lose his Paladinship.
2. He falls to his feelings and doesn't smite her (losing paladinship for letting evil continue)
3. He smites her, but doesn't go further. At this point, it doesn't matter that he's alive and probably is still a Paladin. He's been destroyed.
Alternatively, just Teleport with him to the middle of the ocean and teleport back yourself. Nature will do the rest.