Traditionally, the keyboard shortcut for undo has been listed next to undo on the edit menu. That's pretty discoverable...
Ever time you manually click edit → undo, you'll see the shortcut. It’s not invasive—it’s not some big popup that takes over the screen, or even a neon-colored tooltip that commands your attention—it’s just there, in the background, in case you happen to notice it. Maybe you’re not sure what it means at first, but if you keep seeing it every day, you just might try hitting the sequence of keys at some point...
The best UIs naturally help you progress from a basic user to an advanced user, without you even noticing it. I'm not saying the traditional desktop UI paradigm is the best that can ever possibly be done, but it has had 30 years of evolution at this point, and it's pretty darn strong.
Considering that command-Z is not discoverable either, it’s not too bad, especially as there are undo/redo/clipboard buttons on the keyboard in most cases.