I don't think it'd be that difficult to have a three-man ref panel ready during all games, that could quickly look at the footage from games in progress and make quick decisions. If a ref gives a red card, the player leaves the field until the panel has verified the decision, then if it's not a red, the 4th official sends the guy back on at the next break in play.
There could also be a video observer at each game notifying the panel of any incident the ref didn't see that should be reviewed. If the review suggests a red, the ref gets notified and sends the guy off.
Counter-arguments to the use of video are typically:
1) It would slow down the game (which this wouldn't do)
2) Some decisions aren't obvious, even when viewed from 3 angles in slow-motion (true, there will always be some incidents that not everyone agrees on, but there will also be numerous game and season-changing errors that are very clear and would be corrected by the video panel)
3) The game needs controversy so that there's something to discuss in the media/pub (see #2 - there will always be some incidents that not everyone agrees on)
I'll even waive my consultation fee if they want me to help them set it up :-)