i would suggest looking PAR/pp. it looks like it'll do what you're needing.
on a sidenote, i recently used perl2exe to implement perl code (originally written under unix) on win32 platforms that didn't have the option to install a perl interpreter, and had little to no problem doing so. but it only works for unix and win32 platforms, so that wouldn't float your boat.