in reply to
How much of Perl can be removed?
Perl (miniperl, to be precise) is already available on my PDA, and for anyone else with vaguely modern EPOC, more details can be found on http://www.science-computing.de/o.flebbe/perl/
The readme lists what doesn't work, and it's not a very long readme; if I'm not mistaken, you've got more processing power on a palm, too.
That said, I don't think your question is 'how small could perl be without a file system ?" but "how can I make perl think palmos has a FS ?" because miniperl seems to support a reasonable number of modules, and you're somewhat more limited by perl if you can't use arbitrary modules.