On a rooted Android-devices there is one more option:

You can set up a chrooted Debian-environment (or Ubuntu or whatever) in which you then can have a full Perl.

On my HTC Desire HD I have a Debian with a working CPAN-shell (works even for XS-modules as I have a gcc installed).

You can build the whole filesystem on a PC (using QEMU) and then only copy the image to the SD-card.

The only downside is that with such a Perl you cannot use the Phone-features (e.g. taking a picture) which is really simple with SL4A, but you can access the internet without any problems.