Se me ocurre que podría realizarse poniendo resistencias de distintos valores en cada columna y en cada fila (en las columnas de kiloohmios y en las filas de centenas de ohmios) y puenteamos todas las columnas por un lado y todas las filas por otro.
Posteriormente se metería tensión por un lado y la otra parte del teclado podría ir a un pin del pic configurado en modo analógico.
De esta manera, leeríamos la suma de las resistencias del teclado por lo que podríamos deducir la fila y la columna activadas y, por consiguiente, la tecla pulsada.
No lo he probado, pero creo que debería funcionar, ¿no?