Note that Kryptonite doesn't actually "rekey" the lock but instead gives you an entirely new lock and keys, in roughly the same series type as the one you sent in.
In that case, I think the best solution would be to find someone going back to the USA and sell the lock to them for (price of new lock in that series ) * (whatever hassle percentage discount you think appropriate) - $20 - $8.
You'd essentially be selling that person a new lock after they send it in: the $20 "rekey" fee includes shipping back to the customer in the domestic states and the extra $8 is because that person will need to ship the old lock back to Kryptonite in the first place.
Given that a new Evo 4 is around US$70 - you could sell the dead lock
to someone going back to the USA for $20. They could send it in for +$20+$8 = $48 and get a
new lock. The math isn't very good for the Evo 4 -- much better for
the expensive NY series locks.