Now @INC is all wrong

I think this can be fixed by setting the PERL5LIB environment variable to the desired directories. Delimit the different locations with whatever is specified by perl -V:path_sep

lots of the perl package .... have the old location on the shebang line

If that poses a problem then I don't know of any solution (apart from creating a symlink).

There will additionally be a number of %Config values that need amending - this can be done using the same techniques as employed by ExtUtils::FakeConfig.

However, IMO, by far your best solution is just to recompile perl. If you recompile the same version && use the same config options as the original build && install it into the new location (thereby clobbering the perl you've currently got), then you won't need to re-install any modules.

Cheers,
Rob