To get past the limitations of available I/O lines, wire the LEDs in a matrix. Most of you think of ghosting and blocking when you hear the work "matrix", but if done properly, and it works quite nicely.
The classic PIC16F48 has 13 I/O lines, giving you a 6 x 7 matrix. This can control up to 84 LEDs. Yes, 6x7=42, but remember that LEDs are diodes: if you reverse the polarity of the current, you can light a different LED. Bipolar LEDs do this.
To solve the ghosting problem, you must scan the matrix. This means only one row and column are activated at a time. Before you go on about flickering, it would be doing this at 1-2 MHz. Take a look at your monitor. It's only scanning at 60-100 Hz.
The drawbacks of the matrix is that there is no common ground. Every LED must have two wires leading to the controller. It isn't too hard to do, but it takes longer. The wiring harness can make this simple for users, but it might be rather expensive. The controller board would have 84 pairs of header pins (like the kind on a motherboard power switch header), and the user would have 84 little jumper cables. These cables would have a PC connector on each end, matching the header pins. The two wires would be different colors to indicate polarity. The user would plug one end into the board, and the other onto the LED (the pins happen to be the same type as the header pins, albeit a little longer.)
As for cholin's (my) idea, it would still work, but it would be a horrible rat's nest under there. The best way to do this would be to implement the LED controller on the same board as the keyboard encoder. That way, the LED controller would "know" what was being pressed, and act accordingly.