If speed is very critical, I imagine moving the part that does the interrupt handling and turning on specific lights at specific times off to an outboard processor that does not do interrupts, instead it is dedicated, and just reads the status constantly in the loop. It should do nothing but just a busy poll, and turn on/off lights. It would need some way of getting control updates from the brain processor (another pin perhaps). Otherwise you are going to be spending a lot of time having the interrupt set up the call stack and then undo it. And if that is not fast enough, consider getting a faster processor like an ARM embedded board.
Perhaps you could use a standard 555 type circuit to do the timing, perhaps not.