hi,

I thought I could program any byte to any value any time

Only Atmel makes it possible. They produce many in-application programmable derivatives which may be programmed as you expected. For example, here is from AT89C51RD2 datasheet:

The 64-K byte Flash is programmed by bytes or by pages of 128 bytes. It is not necessary to erase a byte or a page before programming. The programming of a byte or a page includes a self erase before programming.

Regards,
Oleg