Norrlandssiesta:
But the CPU can only do one thing at the same time?
Yes. Fortunately the timers are done in hardware so you can be counting off clock cycles at the same time you are running software. You will want to read about Timer/Counter 1, 2, and 3 in the ATmega328P datasheet. To note the time you just copy the counter register.
You are right that the time it takes to handle the interrupt will limit the minimum delta-t you can measure. If you expect the events to be very close together you could keep the interrupts off and poll the inputs in a tight loop looking for changes. The Arduino can execute 16 instructions per microsecond so you should be able to get resolution of a microsecond or better.
static volatile byte dataBuffer[100];
static voltatile boolean done = false;
byte *pointer = dataBuffer;
static byte oldPins = 0, pins;
do {
while ((pins = PINB & B00011100) == oldPins);
{/*WAIT*/} // wait for PORTB bits 2-4 (Pins 2, 3, and 4) to change
*pointer++ = TCR2; // Note clock counter from Timer 2
*pointer++ = pins; // Note curent state of the input pins
oldPins = pins; // Look for further changes
} while (pins != B00011100);
done = true;
You would then post-process the data buffer to see what order the changes came in. The buffer needs two bytes for each transition. An 8-bit counter (like 2 or 3) will roll over every 16 microseconds. If your experiment is likely to take much more than 16 microseconds you might need to use the 16-bit counter (Counter-Timer 1).