I got the arduino mega 2560, and I looked into burning a new bootloader but you could brick your arduino so i orderd a sd outbreak cause im afraid i will ''code'' it wrong. It is also not my arduino (im on a internship) and they preffer not to do burn a new loader.
If you have a RTC (real time clock) module available, you might find that it has an eeprom included (typically 4K bytes) as part of the module. This will be an "external" eeprom, and is addressed with the Wire library and the I2C protocol. Anything written to it will be persistent through a power shutdown and reboot.