I've used perlapp from ActiveState in the past. It sure as hell would fit a job like the one described to build freestanding executables... They seem to be alot more stable and less "chunkier" than the fully compiled *NIX executables.
... Its worth the money (plus you a get a nice debugger).
Cheers.