how can I package the application up easily?

PAR/PerlApp/CavaPackager/CitrusPerl

without having to ship an entire Perl distribution?

Ship an entire perl distribution, citrusperl makes it easy :)