Assuming that the keypad circuit and the Arduino have a common ground, you can use CD4066 analog switches to do this. Or you can use reed relays or optocouplers if you need full galvanic isolation. You'll need ten digital output pins on the Arduino, which is quite feasible.
The board I am interfacing to does not share the ground with the arduino.
Is it possible to connect the grounds, or is it essential to keep them seprarate? If they must be kept separate (i.e. galvanic isolation), then you will be limited to using relays or optocouplers.
Yes, I think you can reduce the number of switches to seven if you switch on two of them each time (one row, one column).
Yup I think I can have them on the same ground. The device I am interfacing to runs on 12v and I can take power to the Arduino from that, thus sharing grounds.
How can this be done without opto couplers / relays etc?
An optocoupler is simply a LED and a photodiode in an opaque package. If you light the LED, the photodiode (or phototransistor) will conduct. Now, lighting LEDs is something that Arduino users know all about! So that part should be straightforward. The photodiode part of the optocoupler will need to be connected to the switch matrix with the proper polarity (so the the diodes can conduct).
Relays will need more drive circuitry (search in the forums for lots of examples) but will not care about the polarity of the switch matrix circuit. Relays are also likely to be more bulky than optocouplers.
The idea is that for eg, I put Optos 1 and 4 high from the arduino, that will short the 2 wires 1 and 5 connected to the keypad connector making it think key 8 for example was pressed.
Yes, that's the right idea. But, you'll need to reverse the polarity of some of the phototransistors, according to the polarity of the signal on the keypad. If you follow the current path through your circuit, from + to - (conventional current), then it must always flow in the direction of the arrows on the emitters of the transistors.