If it is large it won't fit on the controller as well.
You could use a separate EEPROM chip connected to the µC if the µC doesn't have any/enough - it is not uncommon. The newly released free Kinesis controller design/firmware does so for storing macros and keymaps.
BTW, the EEPROM in the ATmega32u4 that is in the Teensy 2.0 is rated to survive ten times more rewrites that its program memory, but it is only 1K. Using a separate EEPROM chip would be the preferred method.
You would need to implement this in software on the host in either case. That means, baking your own driver that does all this and uses a custom keyboard protocol.
An alternative would be to put a USB hub and a USB drive inside the keyboard's enclosure, and let it all be handled by a simpler software program on the host that reads and writes a file on the USB drive - then no firmware hacking would be necessary.
You could also put that software on the USB drive and run it from the drive. Older Windows machines could run it automatically from autorun.inf on the drive.