Interesting idea, but it may be hard to implement.
Think of your average party of adventurers as a group of special forces operatives. How many spec ops teams include a pacifist?
You're likely to see a scene like this fairly early on:
Paladin: Aha! The giant is unconscious! I quickly lay on hands for one point to stop his bleeding, then begin to tie him up.
Other PC: Screw that! This giant is wearing the skulls of half a dozen people, and he nearly got my skull to add to his necklace. No way I'm letting him go. While the paladin stops the bleeding, I slit the giant's throat.
Paladin: What?! Nooooo!
Adventurers can travel together even if they have different philosophies, as long as their goals are compatible. But most adventurers put "killing bad guys" near the top of their list of goals, and that's highly incompatible with the goal of "not killing bad guys."
Unless the paladin has amazing powers of redemption and can guarantee that the captured villains won't escape to go killing again, the other PCs are pretty unlikely to cooperate with the capture-not-kill approach.
That said, the
Book of Hallowed Might does have some great feats and spells for this effort, including spells that put helpless or willing targets in extradimensional prisons. If the other players are interested in exploring this option (it has to be a party, rather than individual PC, decision), and if the characters are high-enough level, you might want to consider getting the $5 .pdf and getting the player to design a cleric/paladin character who has access to these sweet imprisonment spells.
Daniel