How to create a versioning/history/revision system for contents published by users?

I don't see a single answer with a plugin for your question, because of your personalized workflow.

About the revision workflow

It is your own vision of it, it doesn't seems too bad for your use. But I'm sure that some use cases should have to evolve by the way.

First point that I can see, you must lock the revisions until a revision is in progress AND until it is validated by a moderator. When it is in progress add ARTICLE(revision=progress) for example, to lock it, and avoid users to edit an article at the same time by displaying a message.

Second point, be careful, I believe that the author of the article could update it without any moderation process. For this reason, you'll have to set the ARTICLE(revision=progress) too, while the author updates his own article.

About recording a light version of the revisions in db

You could make a crazy function in php (or other), that creates an array, for each changes, like following :

array('1'=>array('char_pos'=>'250','type'=>'delete','length'=>'25','change'=>''),'2'=>array('char_pos'=>'450','type'=>'insert','length'=>'16','change'=>'some text change'),...);

As you can see, creating, formating and recording this in database could be very awerful and difficult to manage.

I think that there's no way to do versioning with MySQL. You could do something for versioning with an ORM like PROPEL but I don't think that the result will be what you expect...

Here, the better way seems to record the entire updated article for each revision, even if it grows your database. With your workflow you wont read a lot the REVISION table, so MySQL won't have an heavy load for it.

About the comparison display

You could use the Diff-Match-Patch plugin to hilight the updates between two contents, "differences" demo here. I think that SO uses Beyond compare (or similar) to hilight changes between revisions.

To read more about SO technologies, you can have a look at this page.