Krodal:
If the EEPROM is not enough, and you want to be able to change it, use external I2C EEPROM memory. A normal size is 8kbyte, but more is possible.
I'm looking for a cheapest possible solution. My project is to turn Arduino compatible with Gogo Board, an open source platform for educational robotics (http://br-gogo.sourceforge.net).
Now we have a hardare with PIC 18F4550 and a logo compiler generating bytecodes. The bytecodes are stored in the PIC program memory. I want to do the same.
The idea is to do this without modify firmware, to avoid create a different firmware for each arduino type.