Let me see whether I understand you correctly: For each of the two pieces of the keyboard, I need to get a Teensy board, connect it to a Bluetooth chip like nRF8001 (it can be on a breadboard right?), connect the keyswitches to the Teensy inputs in a matrix (with diodes in the correct places for each keyswitch), and then put code on the Teensy that'll (1) get key events by scanning the matrix and (2) transmit those keys using the nRF8001 to the USB dongle connected to the computer. I'll also need a battery to be powering both the Teensy and the nRF8001.
Bang on. Doesn't need to be a teensy, of course, but that's pretty much the gist of it, yes. Software-wise, for the "keyboard" half, you should be able to use Hasu's tmk firmware to do most or all of this with little modification.
For the "computer" side of things, the easiest way to do things would be to use the machine's standard bluetooth (or an add-on, off-the-shelf, dongle) and some custom userland driver software that takes events from the 2 boards and converts them into something understandable. That's where your X MB of storage comes in - all on your computer. If you're using windows, I have no idea how you'd do this.
It would be a bloody sight easier, though, to tether the two bits of board together and use a uC with a bit more "oomph" to do the scanning, lookup, and bluetooth, presenting itself to the computer as a standard bluetooth HID device. Downside is that it would need a bigger battery and a uC with "real time" access to a lot of storage. That's a (relatively) tough one to find, but bare metal coding on something like the Raspberry Pi, or one of the Xmos boards could probably do it. No "base" software to work from, though, the whole lot would have to be bespoke. Or you could stick with the teensy (but only one of them, handling both halves of the board via a wired connection) and use, again, client-side software on the computer to do the expansion.
What you are trying to do is hard.
Read the tmk firmware thread, with the code to hand, and work out what's going on in it. Build it a few times, with different options. That should get you started on understanding how to do the scanning and bluetooth HID stuff.