Regarding your third point, it appears that the Perl Archive Toolkit has a fallback option which allows the use of modules that are already installed but will fall back if needed and use a version included in the PAR file.

I've also been thinking about module requirement issues for my application (still unreleased).

I've decided to offer end users a number of choices:

1. Standard CPAN release, for users who can install from CPAN.
2. Prepackaged for certain Linux distributions (likely just Debian and Ubuntu at first).
3. Binary executable produced with pp, the PAR Packager utility, for those without the knowledge or permissions needed for the first two options.