The LDV and LVW levels are programmable on this chip.
4.6V on a 5V supply, or 2.9 V for 3.3V supply for LVW. If you are using a 3.3V supply, it could be a bit tight.
If you are using a 5V supply, the chip will run down to 2.7V, so you will have a good margin.
The important design point is to arrange the circuit so that the CPU has it's own branch, and the loads it is driving are on a different branch with a separate filter cap.If done right, you can get a good amount of time with a minimum of capacitance (or, like mac said use a large cap). If the CPU is sinking the loads, it will work best, as the "other" cap will be suppling the current.
Since a sector is only 8 bytes on EEPROM, you will want to do a suggested and pre-erase the next block. However, since you do not need to lock out interrupts for EEPROM, you can do this in the foreground and not affect performance.