Try twofish. It was designed to be implemented on 8-bit hardware, and needs only 36 bytes of RAM (if the key is stored in EEPROM).
Try this search for more info.