I came across the micro SD Card shield which is pretty cool if you want to work file based and for instance swap files with your computer.
I found a nice external I2C EEPROM that has 32k byte (256kbit) and has a million writes. The 24LC256 - its pretty cheap (the 400khz that is). I think there is also a 24LC512 that has double the memory address space as the 32kb one (64kb) - that is the same size as my first home computer!
(this guy is a little talkative, but interesting nonetheless - 3 parts)
Advantage of an external EEPROM over the internal one is that if it brakes, you can easily replace it. Its also capable of a lot more writes. And with the I2C serial bus it doesn't eat up that many pins on the main board.
Thanx for your suggestions.