Here's an idea: get an old PS2 keyboard and steal the controller from it. Then you only need 2 pins on the arduino (for the PS2 interface) to read the key codes, and the controller does all the work. You just have to wire up the keys to the controller, in a matrix fashion as suggested. Look at the way the PS2 keyboard is wired for inspiration. You'd even have access to 3 led outputs if you wanted to use them.
There are several libraries and code examples in the playground and forum about how to interface a PS2 keyboard. Since the arduino is only getting key codes, you'd have to write a lot of code to turn those into letters, but it's not that hard. The chip should have enough program space to do it.