I mean, do you ever need to rewrite page 0? You will be much safer for cheap, if you don't. It can contain the bootloader itself; and the interrupt vectors can be fixed - I don't believe this would pose any real problem.
I'll have to think on that one, my ISRs need be pretty fast and an additional ljmp may be a problem.

Btw. if you know nothing on how the block erase really works, you cannot assume it is safe. Some of the EEPROM/FLASH technologies require that all cells are programmed to 00 before erasing - this can take relatively long and I see similar chance of getting this process interrupted than the programming process. The only way how you can be sure is to provide power for the whole time of the erasure (you certainly know how).
if I could guarantee power on, this issue would be moot. anyhow, I'll have to consider this.

But if you'd insist on reprogramming page 0, I'd recommend you to program the jump "backwards": 00 is nop it's relatively safe to program (again, if you interrupt it halfway through programming a byte the result is unpredictible), C0 00 is push 0, that is little harm; and 02 C0 00 is the complete jump to the correct address.
excellent idea. this, of course is in the smallest 'gap' but we all know that Murphy wax an optimist.

Erik