I didn't try it, but I found ExtUtils::AutoInstall:

ExtUtils::AutoInstall lets module writers to specify a more sophisticated form of dependency information than the PREREQ_PM option offered by ExtUtils::MakeMaker.

This module is part of OpenThought and uses CPANPLUS or CPAN to download and install selected modules. With this solution you still need to install some modules before running your installation script... but at least you can borrow some ideas from it :)

Ciao, Valerio