Perhaps another way is to create a disk image? I was thinking of using vmware, cygwin, beos, or a mini linux distribution to provide a completely preconfigured system.

But looking again at Activestate, it's not such a giant download. If perl2exe doesn't work it's probably a good idea to just install Perl.

By the way I just noticed something called PerlApp which "Turns your Perl scripts into executables, so that you can run Perl scripts on computers without installing Perl." It's in the ActiveState Perl Dev Kit, which "makes it easier to build and deploy applications on Windows." An installer maker seems (PerlMSI) to be mentioned too. Interested to hear what these are like.

Updated.