I was asked this question on an interview: given 8 output pins and 8 input pins on a microcontroller, is it possible to read a 10 by 10 switch matrix without using multiplexor and demultiplexor chips? I'm not sure it's possible...
I would do something like this:
I use 7 of the outputs and 8 of the inputs to create a matrix of 56 crosspoints, and I put two switches at each crosspoint, for a total of 112 switches. The 8th output is used to control a set of pullup/pulldown resistors for the inputs.
Scan the array twice. The first time, set Out7 low, and pulse the other outputs high one at a time. Look for any inputs going high. This tells you whether the lower switch at each crosspoint is closed.
The second time, set Out7 high, and pulse the other outputs low one at a time. Look for any inputs going low. This tells you whether the upper switch at each crosspoint is closed.
With 8 output and 8 input pins you can create a matrix of 64 crossings, with a switch at each crossing. You'd have some issues when multiple switches can be closed at the same time, so you might want to use a diode at each switch. And don't forget the pull-ups for the inputs. That's what can be done in the straigtforward way, and my gut feeling is that is what the interviewer wanted to hear.
If there is no need to detect multiple switch closures correctly you could use a diode matris, so each switch can put its unique code on the 8 inputs. No outputs needed, up to 255 switches can be detected (one input state reserved for 'no switch closed'.)
You could cheat by using chips ather than mux/demuxes, like shift-registers, IO extenders, or even microcontrollers. That will teach your interviewer to formulate his question more precise :)
If the pins have both digital and analog capabilities you can get even more creative. I once designed (but never realy built) a system that could read an NxN matrix with two GPIO/analog pins and a bunch of resistors and diodes. The maximum N was limited by the diode drops, resistor accuracies and A/D bits. (No multiple press capability.) Probably not practical, but nice to fantasise about.
Nedd posted and deleted a Charlieplexing suggestion, which requires pins that can both be input and output. Seems to be excluded by your question, but if you use a few pins to make a SPI or I2C bus and connect an MCP23017 style 16 GPIO pin extender...