Or else, M25P32 from ST ...
I believe ST sold the M25P line to Numonyx and the line has been upgraded to the faster M25PE... series.
See the M25PE80 for a sample data sheet.
It's rated at writing 256 bytes in 11 ms.
For M25P code example see M25P32 (warning other compiler).

A full 256 byte per write is probably required however.
Since only erase can convert 0 to 1's overwriting previous of new and following of new bytes with 1's can simulate a one byte write.
Perhaps a low priority interrupt could do the 256 byte write in the background.


Norm