Improving the perl build system to allow relocation without requiring recompilation is certainly do-able and is on the P5P wish list. One way to implement this is to build all executables with dummy and very long paths stuffed into the executable, then write a utility to binary edit them when you move them. Sounds hacky, but in practice it works well and is better than the alternatives.

ActiveState's reloc_perl utility is an example of one way to do it.