Reserve a "recently rewritten" bit in each page of that flash chip's memory.
(Perhaps store that bit in one of the 8 "extra" bytes per page).
As the appsheet suggests, every time the application writes to some random page, also re-write some other page that hasn't been re-written in a while.
To find that other page, scan through all the "recently rewritten" bits searching for a "0" bit. The first "0" bit you find corresponds to the specific page to be rewritten.
Once you've found it, rewrite the data in page while erasing the "recently rewritten" bit to "1".
Since you scan in sequential order, the "recently rewritten" bits towards the beginning are all "1", and the bits towards the end are all "0".
(Optionally keep a pointer in RAM pointing to the page with the last page with a "1" "recently rewritten" bit, or first page with a "0" bit, so you can start searching from that point, rather than starting from page 0 every time).
When you do the search, and the CPU can't find any pages that need to be rewritten (every "recently rewritten" bit is a "1"), then program every "recently rewritten" bit to "0", starting with that bit in flash page 0.
(You can program just this one bit per page without erasing the entire page).
At boot time, when the power first gets turned on,
you'll need to check if the flash is in the "normal" state -- all the pages towards the beginning all have a "1" "recently rewritten" bit, and all the pages towards the end all have a "0" bit.
Anything else indicates the "interrupted" state, in the middle of programming all the "needs to be rewritten" bits to "0", in which case the CPU should finish programming all those "recently rewritten" bits to "0".
(I suppose you could, instead of storing that bit inside its corresponding page,
pack all those bits together in a bit array and store them in a few pages of flash that you reserve for that use. For example, the 7th bit in that array corresponds to the 7th page of flash.
In that case, you'll probably want to invert the meaning of the bit, and program the bit to "0" when the corresponding page is erased and rewritten, and once in a long while, whenever you discover that every page has a corresponding "0" bit, erase all those bits to "1". The result is about the same as what rdeml suggested).