Maybe you could package the whole thing with PAR. While I'm not sure if you want to bundle all the CPAN modules with your script, you could pack your automatic instalation script with PAR.
Comment on Re: telling users how to get CPAN modules
PAR looks interesting -- thanks for the suggestion! I'm a little put off by the apparent complexity of it, though. Maybe I'll give it a shot and see how far I get.