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.
the hatter