24LC256 I2C Flash
The Microchip 24LC256 [1] is an I2C flash memory which provides 32 Kbytes of non-volatile storage, and works with a 2.5 V to 5.5 V supply. Unlike the SPI flash memory chips, you don't have to worry about erasing the memory before writing; that's all handled automatically. The only consideration is that it's more efficient to write 64 contiguous bytes at a time, but you are free to write single bytes if you want to.
The interface functions are compact enough to run on any uLisp platform, even an Arduino Uno:

The chip has a defailt I2C address of #x50, but there are three address lines which gives you a choice of 8 different addresses. Here's the uLisp interface:
(defvar i2caddress #x50)
(defun write (address data)
(with-i2c (str i2caddress)
(write-byte (ash address -8) str)
(write-byte address str)
(write-byte data str))
(waitready))
(defun waitready ()
(loop
(with-i2c (str i2caddress)
(when str (return)))))
(defun read (address)
(with-i2c (str i2caddress)
(write-byte (ash address -8) str)
(write-byte address str)
(restart-i2c str 1)
(read-byte str)))
Because writing can take a significant amount of time, after writing to the chip you need to wait until the device is available on the bus again.
Here's a test routine that writes the numbers 0 to 255 to the memory chip, and then reads them back and displays them:
(defun testwrite ()
(dotimes (i 256)
(write i i)))
(defun testread ()
(dotimes (i 256)
(princ (read i))
(princ #\space)))
- ^ 24LC256 Datasheet on Microchip.com
