You can upgrade hashes offline as well. You just hash the existing hash with the new algorithm/configuration and remember algorithm, salt and any other parameters for all previously used algorithms. If you have all that information you can take the same path to verify the password and replace the chained hash with a simple hash that's faster to calculate.

Indeed, though I suppose you've got to hope that the keeper of the passwords gets their hands on a similar level of processing power as the attackers do, with which they can increase the encryption work factor.