As a user, I notice that ExtUtils::MakeMaker already includes mechanisms to signal the fact that some needed modules aren't present. This is used by CPAN to ask the user if the dependencies have to be added to the list of modules to be installed. These two modules should be a good starting point to figure things out.

Moreover, maybe you should also take a look at PAR. I don't know it at all, but it probably already includes mechanisms to skip the installation of already present modules, among other goodies.