A couple of questions:
Will his desire not to kill be part of his paladin's code? I.e., will he lose his abilities if he breaks this taboo? If so, I think there should be some kind of institution for redemption in the world. Maybe there's an island ruled over by a high-level pixie druid; they'll take on anyone who detects as evil, erase their memory (with those cool arrows), and teach them how to be good.
The reason I suggest this is that the paladin won't be able to deal with all the bad guys he encounters. Indeed, even the local militia won't be able to handle most BBEG's once you're up into the higher levels. If he encounters a drow war party on its way to slaughter a bunch of innocents, what will he do? Give them a good talking to? Beat them into submission, then hand them over to the town guard? Avoid them, and try to save the innocents in another way? How far will he go to not kill someone? Would he be willing to beat up all the drow, then cut off their hands to prevent them from using their weapons? And when he starts seeing the bad guys for the second and third times (since he didn't kill them before), will he be able to change his mind?
How far will this taboo go? Will he be vegetarian? Would he kill a shambling mound?
I might suggest that he only be willing to kill when he deems it absolutely necessary for the greater good. Maybe put a restriction on it (allow him 1 killing/level). You could also narrow the focus to a few types: don't let him kill humanoid and monstrous humanoid types, but let him kill oozes, undead, plants, animals, beasts, etc.
This sounds like a fun character. I hope it works out well.
Spider