It doesn't have to be fast - as long as you have control of the program at the "sending" end. Use a pic with at least a couple of hundred bytes of RAM and buffer the incoming data before you do a write to the EEPROM. You would send a buffer full, then pause and wait for the PIC to send a CTS or ACK, then send another buffer... As long as you do it this way, you can write as slowly as you need to in order to write the FLASH.

I do a similar thing now, were I create a 2056 byte buffer (2048 bytes of data + CRC + control) in the RAM of an 18F8722, then send EEPROM data to the PIC in Intel Hex format over a 115K baud serial line, and when it is all received, check the CRC, convert it to binary and do the write to EEPROM. After programming the chip reboots (which destroys the 2056 byte buffer so I can now use the RAM space for my program) and starts with the new configuration. In my case, the 1024 bytes of EEPROM was inside the PIC, but it wouldn't have to be.

This was really designed as a fast way to configure a whole bunch of chips with the same setup, but you could adapt the technique for boot loading.