Now here’s a couple of ideas ...

(1)   They will definitely want an installer.   Okay, I still use (and I still like) InnoSetup.   Make the process of installing the thing painless.   Inno has a lot of Pascal-esque... script capability, including the ability to call DLLs (including “temporary” ones that are never permanently installed).   I think that you will be able to set up the Perl runtime environment completely, using what it has to offer.

(I’ve used several 16- and 32-bit installers over the years with my “still(!!) bread-and-butter” database-repair product, and Inno is the first – and therefore, last – product that I have been truly happy with ...)

(2)   Maybe think in terms of having “the installed icon” actually run a launcher, which silently sets-up the Perl environment, spawns a copy of the Perl interpreter as a child process, then goes to sleep waiting for it to finish ... all without ever drawing attention to the fact that it even exists.   Cobbling such a thing in the dot-Net world, using VB (I don't think you'd need to travel next-door to C#-land for any of this ...), would be a very easy thing to do, and the end-user would never know nor care.   From their point-of-view, double-clicking the icon would launch “your program.”

(3)   Thus, you have actually side-stepped the apparent “requirement” of bundling Perl into “the executable that is launched by the double-click.”   This requirement would no longer exist.   Inno can set-up “a fairly complicated file/directory structure” without calling attention to the fact that it has done so, and the launcher-EXE can set-up and launch (even) “a fairly complicated Perl runtime environment” without calling attention to the fact that it has done so.   Between the two, I daresay that you will have a practical solution to your problem.