You could use pin change interrupts in addition to the two external interrupts on the Uno.
Using one interrupt, the method can't discriminate between pulses that arrive closer together than the time it takes to acknowledge the interrupt (the "interrupt latency") and sample the inputs.
Tell us more about the pulse streams: frequency, on time, etc.