The Portable.pm is not really what I want here as that would require the users to change their code but I just found an old e-mail thread with kmx in which we talked about this issue. So maybe I misunderstand what Portable does.

The relocateperl of Citrusperl might do what I need here, but it is written in C and I could not find its source yet.