Assuming that licensing is not an issue, you can just bundle and deliver the "outside" modules as part of your application.
If licensing is issue, you could probably easily deploy the select group of CPAN modules you want to use as distinct and differently-licensed bundle of software.
See also: A Vision for Easy Web Application Deployment for Perl
Wow! You hit the nail on the head there (and apparently opened a can of worms too! Better you than me).
That's pretty much where I'm heading. Self install Perl web apps that you simply place in your CGI directory, click and go. PHP'rs do it all the time. The code is bundled up with the CGI install script, which gets neatly extracted into the correct directories based on the running CGI env and help from the user. I see no reason why Perl can't do the same, provided you're not tied down to installing 3rd party modules in places the user doesn't have access to (or at the very least the self install could check for required modules and inform the user of what's missing).
BikeNomad had the right idea with the Self-extracting Perl archives code he posted (although I'm not sure why he felt the need to encode it).