You can't change the old keys any more, you already realized that, so I'll skip that discussion. I'd change the order of things to do a little bit, though.
- Set up a reasonable, working backup. One, that will not fail if you format the wrong drive (because you forgot to unplug the backup disk). Do it now, or you'll likely never do it (on one hand because you're "that kind of guy", and on the other hand because this probably matches most people).
- Verify whether your backup is really working by restoring and comparing its contents.
Now (and not before) you're ready to perform any kind of work on your computer, no matter whether it involves OpenPGP keys or not.
- Create a new set of key pairs.
- If you use GnuPG 2.1 (or newer), a revocation certificate will automatically be generated, otherwise do so manually. Apart from having the revocation certificate in the backup you already configured before, consider printing one (QR codes are handy for reading it again). Put it in a safe place, for example a safe deposit box or simply with some trusted family member or friends. It's unlikely you mess up you working copy, backup AND this paper copy not in your house at the same time.
- Verify both your new set of keys and revocation certificate are in your backup by restoring them.
- Publish your new key.
- If your old key received certifications or know other people using your key, send a key transmission statement explaining the situation, prompt others to verify your new key again and not use the old one any more.
- Get your new key certified as needed.
- Wait until the lost key expires anyway.
You can't really do anything to notify others throughout the key server network about your old key being lost. Putting a note in other keys' user ID will not really help (people probably won't even read it), but at the same time be visible forever to people looking at your keys. Instead, better issue a third party revocation, which will not be considered valid (as your old key does not list your new key as allowed revoker), but hopefully all relevant OpenPGP clients will issue a warning message on something being fishy (GnuPG does).