You can also try RAMTRON's FRAM, like FM1608: it is 8K x 8Bit, has 10E10 read/write - cyles, no battery is need. just take care of the CE - pin: you do not have to tie this pin permanently to ground, no, you have to make falling edges on this pin (make a logic with ALE and your original CE).
if you use this FRAMs be aware that you put just seldom stored data in it and do not use it as external working ram, as you need it for c-applications. if you do this you will be finished with your 10E10 read/write - cycles within some hours !