Role Play solution
The thing I like about this story is that it is plausible. Punishment should contribute to the shared goals of the two gods - not cripple the cleric necessarily. This is how I would handle a low level change.
I would give the cleric a small tap on the wrist (literally). The cleric would have to be willing to place his hand in the mouth of a World Serpent Statue and submit to the will of Tyr. Hey thats the diety after all. The cleric would not know what will happen in this case and the clerics of Tyr must be really clear "Is this the center of your heart????". (I'd have a few clerics present without hands just for atmosphere

)
If the character is accepted by Tyr he will hallucinate the serpent crushing his hand and draining his magic then collapse into a fever. In the Fever Tyr himself or mory probably a valkirie will appear to him and give him a new set of spells - domain change, the works. (the character's only 3rd level after all).
When the char awakes he is to understand that his God is one of war and action. The Cleric will renew spells 1 day in 7. After each vengeful death accepted he will receive spells on another day in 7. He must surrender any items signicant to his previous diety - including any weapon that has ever held a blessing - and must either destroy them (bad idea) or offer them to his old church. The Church of Tyr will advance the char similar equipment.
(He can receive an experience bonus if he can arrive at a gold price for his person and give them that much as well to pay them for his body. Until he does so expect relations to be strained. If he needlesly destroys what he once held sacred that would be an evil act in my estimation and his former deity will consider him so.)
Limitations:
He must throw the final stroke and send the soul to the other world or it will not count for his quest.
If it is only a monster of the same race but of no actual relationship to his capture he must return the right hand of each creature slain to a consecrated alter to Tyr. If it is actually a creature involved in his torture it happens immediately - he also receives a blessing for the remainder of that encounter.
Until he has achieved this he may not consecrate alters himself or perform clerical services for others. He can not honourably fulfil his duties until he has proven himself.
No more than one hand per encounter will count. The rest of the slain are to be piled and offerred to the pantheon as a whole. Lawful deities will not deny their fellow dieties.
After the seventh successful encounter he will be given a vision and a sense of peace. Other information might be imparted to him - whatever the DM wants to put.
Anyway thats how I'd handle it I think.
If he had truly uber powerful items that were hard to replace I'd have him make a quest for each one.
Do people think this is too hard?
Sigurd