Have you worked with AT25128A flash?

It is very important for me that i could write to single bytes in flash without the need to erase a whole page/sector/block in flash.

This flash says in datasheet:
"All programming cycles are completely self-timed, and no sepa-
rate Erase cycle is required before Write."
https://www.atmel.com/dyn/resources/prod_documents/doc3368.pdf

Does this satisfy my requirement, or do its not enough to know?

Thank you.

Yes. Of course you can ALWAYS write single bytes in ANY flash. What you can not always do is overwrite single bytes.

Dan