I had started to re-do some of my GLCD code to support these things last night...then I got to wondering what they cost.
$40USD at Digikey! No thanks!
But obviously, I agree, EEPROM, not good.
If you've already got half of a circuit built for the 16F876A, just switch over to an 18F2620 (or 2685 for even more code space). Practically the same pinout and aside from a few register changes (and config changes ), it'll almost drop right in.
In my latest project, if I wasn't using so much of the onchip ram for other things, I'd keep the font table in a large array and use it from there. As it is, I only keep the alpha & number character 'font' in an array and keep the rest in the eeprom.
The '4620 has ~3900-ish bytes of ram. You should be able to double-buffer one screen in the ram easily, modify it there, then shift the whole thing out in one shot, if that's the way you want to go.
Could use an external FRAM for buffering the data though...