Using the internal eeprom should work for your application. They are conservatively spec'd for 100000 R/W cycles to an address, so for 250000/10 you are comfortably within spec even if you do all your writes to the same two addresses required for the integer.
But you could use a wear leveling scheme and safely write every cycle. Because your data is monotonically increasing, then the method is very simple, because the data becomes its own index to its location.
Type your cycle data as unsigned long and you write it to 4 bytes in the 1024K eeprom. With each write, you will move this storage chunk progressively around in the eeprom to 256 possible locations.
There will be a data value in eeprom bytes 0:3, then the next at bytes 4:7, then the next in 8:11 etc. When you get to the end of the eeprom you start around again. When the power is on and the program is running the management of the next write location is straight forward.
When power is cycled, the program needs to find where the last written chunk was located, maybe use that value for something, and to start writing again from that location.
The way to do this is to start reading the eeprom from address 0 in 4 byte chunks and test each value against the next. When the value at an address is not bigger than the value in the previous address (remember to be incrementing addresses by 4), that is where to write the next value. You will need to start off with the eeprom at all 0's so that the comparison of each stored value to the next will work on the first pass. If you find that all 256 locations contain increasing data values, then your next write will be at address 0.
You will basically share the 250,000 writes across 256 locations with a little less than 1000 writes in each byte.
Your first task is to write your data 256 times, at sequential locations 4 bytes apart. Then practice reading what you have stored.
When you are comfortable writing the data to sequential locations and sequentially reading it out, you can move on to comparing each pair of sequential values. Test if a value is larger than the last one, and if it isn't you have found where the next write should be. The testing routine should be part of startup() in your final program.