They had a situation like this in the finals at the europeans and it worked OK but there was a lot of attempting to influence the 3 referees.
I don't see how a coin toss can be described as unfair, in my opinion it is exactly the opposite. It's a 50-50 decision, ie fair.
If you are unable to sub your opponent in 10 minutes then you have to accept that the progression will be decided by chance.
In my opinion this would encourage people to go for the finish in the last couple of minutes rather than stalling for the last couple of minutes.