Have you tried perl2exe? It will compile (well, package) programs into an exe that doesn't require Perl to be on the target system.