I've always thought that it's a case of knowing the key of a song, what chords are used, and those scales, and then a sort-of-trial-and-error process, but with a bit of an inclination due to a knowledge of music theory.
Then again, I may be completely wrong.
No, I'd say you're spot-on.
Start with single-line melodies. Learn to pick them out by ear. There's no shame with starting out with "Happy Birthday" and "Twinkle, Twinkle Little Star".
Tune your uke by ear every now and then. It trains your ear to hear how similar (or not) two pitches are.
Develop the ability to "hear" when a song changes from one chord to another. You don't have to know what the chords are yet, you just have to be aware that the chord has changed from
something to
something else. Most people who have been playing for a short time are pretty good at this already.
Next, work on picking out bass notes. Not the bass line, per se (although that would be nice!), but just the basic root of each chord that goes by. That's going to (usually) give you the letter used in the name of the chord.
Then, work on figuring out the full name of the chords. If you know a bit of theory (scales, chords, keys) then the bass and melody will be
big clues as to the full chord.
Once you know the chords (either by ear or from a chord chart) and the melody, try to figure out a way to play the melody while also tossing in a full chord now and again. Knowledge of chord inversions will be a big help here, since that will give you more ways to toss that chord in with any given melody note. Now you're getting into the WS64 neighborhood.
(Note: I can do those last step pretty okay on piano, but I'm lousy at it on the uke. I'm not even in the same state as WS64, much less neighborhood!)
JJ