Non volatile memory options?

You could use an I2C eeprom like this 32k byte dip part, 2 bucks at sparkfun: I2C EEPROM - 256k Bit (24LC256) - COM-00525 - SparkFun Electronics

some code to get you started here: Arduino Playground - I2CEEPROM