1. Even if you'll compile using perlcc perl still must exist on a machine that will execute your program
2. if you're compiling anything using Cygwin, your executable will depend on cygwin1.dll and other auxiliary files.
   A bit less dependancies will be if you're compiling using just perl for Win32.

To guarantee that your program will execute on machine without perl, just distribute perl files with your executable.
May be you can strip most files and distribute just minimal set. But in this case do not perform perl installation procedure, just arrange your executable to be able to find right perl56.dll and other necessary files. (place them in a directory with your .exe file)

Courage, the Cowardly Dog