External EEPROM is one of the oldest technologies for permanent data storage. It is usually controlled by protocol I2C and does not have a 5V voltage problem. If a small EEPROM in the Arduino is not enough to you, you can find a wide range of memories that you can use.
EEPROMs are produced in different sizes. All sizes are in bits, so for normal use in bytes you need to divide the capacity by 8.
List of blog articles describing how to control external EEPROM.