For smaller projects, we still do something similar to your current procedure in that we lock the live instance to read only by blocking all users with edit rights, than dump the database, upload it to a stage instance, perform all updates we need there and once satisfied with the results, we switch the stage instance to become the next live version. But even for small instances this is painful and far from a good solution.
In two bigger projects, we are in the same boat as Jeremy in that the whole setup is way to complex for deploying complete database dumps, especially since we can not afford to lock down the instances to read only mode just for some updates.
For those, we have used Migraine to some extend (see also this related discussion). It is not a Drupal module but a python script that we adapted a bit to our needs. It aims to create somewhat structured dumps, separating user supplied content from settings and other stuff, thus allowing for more selective update and staging strategies. But given the more or less chaotic Drupal database structure (especially the lack of referential integrity enforcement), using this approach needs constant tweaking when adding new modules and is pretty risky, as one needs to make extra sure to dump/update only coherent sets of tables.
We try to minimize the need for 'wholesale' dump/update operations by using the update functions of our custom modules and I like Jeremy Frenchs suggestion of adding a 'dummy' module just for the ability to add update functions for other settings!
All in all, updating/migrating Drupal instances is a big pain right now and I hope there will be a more coherent solution in future versions, although I can see that it is difficult to come up with a generalized approach given the current database schema and the amount of custom modules with individual additions out there :/
PS: Backup and Migrate is a Drupal module that seems to take an approach similar to that of the Migraine script, but I have not used it yet.