I'd suggested installing Eclipse and follow the Android documentation to get a development environment up and running, this allows testing your apps on a virtual Android device, you can alter the hardware specification and Android version for testing/benchmarking purposes.

As for SL4A, this looks quite interesting, I'll play around with this when I get home this evening. The only problem I can see is that your application will have a much larger filesize than a native JavaApp, which impacts device performance (most people don't have Apps2sd**) and as you say, potential impact on bandwidth use, which may result in a cost.

The FAQ suggests that you can install (pure) Python modules by coping them to the appropriate place, perhaps this is the same for (pure) Perl modules.

Update: Do you have a terminal emulator installed on your phone? You could have a look around to see if cpan is part of the perl packages SL4A downloads.

Update 2: Also, I'd be curious as to know if when publishing a script, what the access permissions will be? The SL4A requirements (essentially wanting full hardware control and access to all your data) may be off putting to end users.

** Note that with most Android builds, applications are installed to the phones internal memory, which reduces the free RAM available to the system. I use Cyanogenmod, which allows me to specify where things get installed to, among other improvements.