Use self-fluxing enameled wire. It's insulated with an enamel that melts/converts into flux at soldering temperatures, so all you need to do is wrap a turn around the post of each switch contact for a column, then add solder to complete the connection. Some are sold in a convenient pencil-shaped dispenser (http://en.wikipedia.org/wiki/Wiring_pencil ).
I've always wanted to build a keyboard for fast typing, with ultra-light low-travel leaf-spring switches that have a more "bouncy" feel. When trying to type at 160WPM+ it matters far less what kind of sound or tactile feel the keys produce as you care more about the key actuating immediately when hit and providing some spring action to help the finger back up afterward. A leaf-mounted keycap has essentially no sliding friction, which means very little difference in force required between hitting it obliquely or perpendicularly.
Isn't buying a premade MCU board for a "keyboard from scratch" cheating a little? I'd go with a deadbugged 8749 in a DIP-40 package, the classic MCU for a keyboard controller. :-)