If you don't expect people to install more than this one Perl script, I wouldn't install a full Perl, as it easily takes up more than 100MB of disk space. That's plain ridiculous. Instead, I'd look at Perl script packers, a la PAR, to create an executable comprising of the script, the Perl binary, and the modules.

About a year ago I had a good look at a few of the freely available options; you can see my findings in a blog post.

Personally, I liked crazyinsomniac/PodMaster's solution, PerlBin, and Cava Packager, best. I haven't looked at it since then, but I expect that the latter likely has evolved a little; I don't think so, about the former. That unfortunately means that it will most likely not work for the more recent perl 5.10.x.