this leads me to believe it might not be safe to flip a bit to zero without erasing the byte first

Before a location in the EEPROM is written (programmed), it should be erased
to assure that all bits in that location are high. The process of writing data into a location
of the EEPROM removes fuse connections from the fuse map for all zeros in the data.
Ones in the data cause the fuses to be left in place. Thus, all locations need to be
connected prior to the write operation.