Don't forget the EEPROM. 512 bytes (1024 in the newer arduninos) is not too bad, especially if you pre-tokenize things.
Someone has written an interpreter that would process basic-like statements from the serial port and such, but they called it something weird and I can't find it 
There have been a couple generic AVR projects along those lines that could be ported to Arduino: