minimizing downtime when upgrading

Anyone have any tips for minimizing downtime when upgrading?  So far
we have done upgrades during scheduled downtimes.  Now we are getting
to the point where the time required for a standard dump/restore is
just too long.  What have others done when downtime is critical?  The
only solution we have been able to come up with is to migrate the data
on a per user basis to a new database server.  Each user is a
merchant, and the data in the database is order data.  Migrating one
merchant at a time will keep the downtime per merchant limited to just
the time it takes to migrate the data for that merchant, which is
acceptable.

Any other ideas?