Big +1 to the idea, but it's not going to be pretty; there is a lot of baked-in MD5 stuff around.
2. In v19, allow upgrading with MD5 passwords and allow authenticating with them, but disallow creating new ones (i.e., restrict/remove password_encryption and don't allow setting pre-hashed MD5 passwords).
Certainly not remove it, that would break lots of things. Perhaps one release with a strong warning when md5 is used, that cannot be disabled, then disallow new ones?
3. In v20, allow upgrading with MD5 passwords, but disallow using them for authentication.
Again, maybe a release that complains real loudly but still allows it?
4. In v21, disallow upgrading with MD5 passwords.
You mean having pg_upgrade refuse to go on? Or maybe have it empty the passwords out?