The only way to do this would be to announce a new version of the protocol well in advance. It would need to co-exist in the same blockchain with the existing keys and transactions and be adopted over time.
- First, the client software with support for the new scheme needs to see widespread adoption before anyone can use the new algorithm
- Once that has happened, early adopters (probably mining pools) can start creating keys in the new format and the blockchain will accept them.
- If that worked well, the standard client will default to making new keys
- Some more time down the road, everyone can agree that transactions can only be done to new keys, forcing the "old money" out of the system eventually