Whittling perl down that far is not likely, unfortunately. Even if you tossed everything you're still going to end up with a good-sized executable. (My 5.005_03 perl is about a half-meg)
The bigger problem you'll run into with perl is the size of individual segments of code. IIRC the palms can't handle segments larger than 64K. Chunks of the tokenizer and parser are, IIRC, larger than that.
If you do take a shot at this, consider one of the pre-unicode perls--5.004_05 would be a good one. It's got plenty of Pure Perl Power, and since you'll be running without libraries the fact that most things won't build on it any more doesn't really matter.