First, I'd say dump the wireless requirement, at least for the early prototypes. Once you have a prototype that works, and you've picked up some electrical knowledge along the way, you can add-in wireless after-the-fact. Assuming you've designed the firmware well, it should be fairly easiy.
Then, I would say the approach I would recommend would be to target a microcontroller that can easily emulate a HID device.
The cheap and easy approach, and the one I would take, is to buy an arduino leonardo. The leonardo (and the makey makey, for that matter), both use an ATmega32U4, which is a microcontroller with an integrated USB interface.
Since the USB interface is part of the microcontroller, rather then a separate, purpose-specific device, it can be configured to act as a arbitrary HID (human interface device). In fact, there already exists a library for using a ATmega32U4 as a USB keyboard.
Now, lastly, you are basically almost certainly going to have to use a switch-matrix of some sort. Aside from designing your own circuit-board, with an enormous IC (such as a 144 pin TQFP, or similar), you are not going to have enough IO lines to have a dedicated input for every key.
This is fine. Switch matrices are a well-understood practice, and if you're really concerned about button aliasing, you can add a diode for every switch, and make the circuit-board incapable of aliasing.
For the moment, I would suggest you buy an arduino leonardo, and throw together a prototype. I think you're underestimating the mechanical complexity of this build significantly, and having the electronics you need to at least get the system talking to the computer, and acting as a keyboard will let you start poking around at the mechanics.
You are right in thinking you can use relays. However, you are wrong in thinking you can switch just the ground and leave the signal connected.
The shield round the RCA cable is only one of the ground routes between the TV and the video source. They are also connected via the mains cables, unless you're running from batteries. With the ground disconnected as you were envisaging, the signal would return to the video source through another route, one which is very noisy, high impedance, and just generally messy. So your signal would still be there, but massively corrupted.
Secondly, as that signal will still be there, so will the other signal, so you will have both signals there all the time fighting with each other.
A relay, as commented, is a mechanical switch. It is an electromagnet that moves a chunk of metal (armature) and forces it against one of two metal plates (contacts). The "common" connection is linked to the armature, and the "NC" and "NO", or "Normally Closed" and "Normally Open" pins are connected to the two contacts. A spring returns the armature to the "NC" position when power is removed from the coil.
So, with 3 relays, you can have 2 groups of 3 signals switched. The TV end goes to each of the common pins, and the incoming video signals go to the NC and NO pins, one for each video (make sure you keep them the same for all the video signals ;) )
As you only have 2 relays that is a little tricky. I can tell you now that it isn't possible to switch 3 signals with 2 switches. So you need to add a third relay. You could either buy 2 boards and control them individually, or you could get 2 more extra relays that run from the same power and use one of the on-board relays to switch the other two relays. Or to simplify, those two extra relays could be one single "double pole" relay - a relay that is like having 2 relays in one box with one coil - it switches 2 signals at once.
Best Answer
Without a hot air gun suitable for SMD rework, I'd go at the switch with a Dremel, being careful not to pull the pads off the board, and then clean up each pad with an iron and braid. Then lay down whatever connections you'd like by running wire wrap wire