Interrupts are not the way to go, but it is certainly possible to read an input pin at a rate much faster than 125 kHz.
Use direct port access and poll, for example, wait until PORTB, pin 5 goes high, then read PORTD, pin 3:
while (PINB & (1<<5) == 0); //poll PORTB, pin 5
x = PIND&(1<<3); //read PORTD, pin 3
The second read will happen just a couple of 62.5 ns processor cycles after PB5 goes high, but of course there will be some jitter because of the branch.