So after a bit of fiddling with different methods, I came up with the following circuit. It's a bit clumsy but does the tasks a PIC would have to do but in solid state. The one below will produce a 4 bit output for a corresponding key press.

The circuit will latch a 4-bit binary code at outputs Q0-Q3 with a value that corresponds to the key pressed. If no key is pressed then all outputs will be a 1, reading 15 (1111)

There are 2 exceptions, the star key which produces an output of 10 (1010) and the hash key which generates 12 (1100).

The circuit is driven by the astable made from IC1a/b and runs at about 50 Hz. It drives IC2, a 4-bit presetable binary counter which generates the ouput code to be latched by IC3. The astable also drives IC4, a decade counter whose first 3 outputs test the switch status of each row. The next output resets the counter and drives another decade counter IC5. This provides the signals to drive the rows of the keypad. When a key is pressed, the correct column is detected by the AND gates to latch the current binary output of IC2 and the value of the key being checked.

Because of the position of the "0", it would generate a code of "1101" so an extra AND gate is used to detect row 4 column 2 key which resets the latch outputs to 0000 over-riding any value ebing latched but producing the correct code.

If no key is pressed, an AND gate wired as an inverter, IC1c takes the low signal from the carry-out when 15 is reached and freezes the counter. This is then latched by Q5 output of IC5 which happens on the 15th count.

Since the first key is "1" and the counter IC2 normally starts on 0, it is preset with 0001 rather than reset. The output latch IC3 is actually another 4516 presettable counter but the counter controls are not used.

A key detection will take a maximum of 250ms but this can be reduced by increasing the frequency of the astable and reducing R1.

The circuit has a drawback in that there is no strobe output to let other circuitry know a key has been pressed but I am sure this could be added easily enough. There are also 7 IC's compared to one PIC which after all is the main reason PICs were developed in the first place, as a communication interpreter.