360/256 = 1.40625 Deg/Step is the only real problem that I see and as to storage a 24C02 would be more than enough external storage and relieve the 328's eeprom cheap and easy to use too.
Like I said in my prior brainstorming thread, I wouldn't write the new rotary encoder position to the 328's EEPROM until a second or so has expired. So you probably want to have an interrupt handler calculate the new position and set a flag saying the position is dirty and the time it became dirty. Then somewhere in the main loop check that and after a second expires write it out. If another interrupt comes in in under a second, the time is updated so the write never occurs until a second has passed. This should cut down on the number of writes dramatically.