The reason PerlApp only works on NT (not 9x) is the lack of functions for manipulating EXE files. Obviously having OS support for that makes writing any kind of compiler easier!
Specifically, it works by taking the stub EXE and sticking all the files to bundle as "resources" to a copy of that EXE. I'm pretty sure it's uncompressed, too!
Instead of using the resource fork as an archive, you could implement it as a tarball concatenated after the stub, as with a typical self-extracting archive. Then you would not need those exotic functions, and the source for the stub would be portable (as opposed to using OS-specific features to read the resources).