Take a look at the 'autobundle' command in the CPAN shell. This creates bundle file based on the content of @INC. You can use the resultant file as input to a 'CPAN install' command. This doesn't get completely away from 'reinstalling everything' (because that what it does under the covers), but it reduces that amount of hand waving you have to do.

According to my copy of Perl In A Nutshell the code looks like this:

perl -MCPAN -e 'autobundle'
[download]

This writes a file in your $CPAN_HOME/Bundle with a name that contains the date of the run and a disambiguation counter; for example MyBundle_2009_10_28_00.

You take a copy of the MyBundle file over to your newly built machine, install Perl, issue the command:

 
perl-MCPAN -e 'install MyBundle_2009_10_28_00'
[download]

and Bob's Your Uncle.