What lead time is required to change an already submitted flight plan?
The flight plan can be changed by the minute, as long as the two governments and the two airports and the airline agree on this.

As it seems like the government pays the airline to just take off whenever they are allowed to, take the airline out of the equation.
Likewise for the airports, since they are either state-operated or have a concession which states that they have to assist in lawful deportations, emergencies or state affairs.

This keeps two governments in, which have to agree on a time and the who-pays-whom-how-much for the deportation to really take place. In fact, I think this is the only reason why the plane is not yet airborne - because of two governments playing their diplomacy games.