However is it necessary to erase a block or can single bytes
programmed new without prior erase the whole block.
The nature of flash is block erase. Many users of byte programming have been severely surprised by endurance problems. (Some/All?) Flash chips with byte program actually have a little RAM inside and erase a block for each byte write. Thus when you have written 10.000 bytes the endurance is shot.

for the 668 and other block erase chips do this:
Once you have erased a block, you can program single bytes id they can not be ff, if they can you can program (a small) array. The method is known as a "walking write"

Erase the block, make what you store recognizable in "a byte is never ff" (structure/array/byte store. That way last written is ff found - 1, where to write is ff found. Then, when you are at the end of the block, you must erase and start over.

Erik