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.