I still think you should have more than enough storage on an 18F452.
Yeap, I must have been smoking something. No way to fit it in.

The part you highlighted is very cool (fast as SRAM, but non-volatile like SEEPROM). The 16k part will be great for 1024 WORDS, but will only fit half of the 1204 LONGS.