Anyway, it seems that I should be able to feed the pulses from all 4 lines to some sort of circuit which would then toggle its output when any of its inputs change. That way I only need one interrupt to call an ISR which then checks the state of four pins and calculates rotation. By the way, I may need the resolution provided by following all 4 transitions, so just interrupting on one of the quadrature lines might not do the trick.
As Aeturnalus stated there is pin change interrupt function.
But for the record what you wish to do using an existing external user interrupt pin is pretty easy to do, just wire a common OR gate using two diodes and one pull-up resistor. Wire each channel to a diode cathode and also to a digital input pin and set the interrupt to CHANGE mode. Encoder common wires to ground. Then in the ISR read the digital input pins and compare with last reading and decide if its a + or - step.