You can run a timer at 16 MHz so you an get a precision of 1/16th of a microsecond.
You can use the Pin Change Interrupt feature to run an ISR when any of the pins change. As each pin goes HIGH, note the pin number and timer count and disable the interrupt for that pin. Compare timer counts to get relative timing.