Rather than using the associative array as the event queue, keep a separate integer-indexed array. Loop over an explicit index variable rather than using the internal array position.

$events = array_keys($a);
for ($i=0; $i < count($events); ++$i) {
    ...
    /* if there's an event to add after $j */
    array_splice($events, $j+1, 0, array($new_event_key));
    $a[$new_event_key] = $new_event_data;
    ...
}

Rather than using the associative array as the event queue, keep a separate integer-indexed array. Loop over an explicit index variable rather than using the internal array position.

$events = array_keys($a);
for ($i=0; $i < count($events); ++$i) {
    ...
    /* if there's an event to add after $j */
    array_splice($events, $j+1, 0, array($new_event_key));
    $a[$new_event_key] = $new_event_data;
    ...
}

To keep things more cohesive, you can package the two arrays into an event queue class.