I think not picking a key is the problem. Remember you write a first draft first - after you get the first draft going then you can flavor it out. I write lyrics first, if I do not have a story there is no need for the song. Plus the lyrics will later help with note placement. One melody note for each lyric word. Happy takes two notes as does birthday, then to and you take one note. Simple stuff that in the long run fit together.
Next pick a key - the one the supposed vocalist likes. Then I get a cookie cutter chord progression for my first draft. Why? I cheat. The melody and the chord should share like notes so I use the notes of the chord's pentatonic - which gives me plenty of notes for a first draft - for my melody.
Chord progression for verse movement and chord notes for the melody. Three verses with the same progression, probably the same melody for each. Then one chorus and there is a first draft. You can start with the melody and work from there, really does not matter what comes first, however, all the steps have to be in place before you finish - melody, harmony & rhythm plus some lyrics if you like.
Then you can start getting fancy. It all starts with the story, then pick a key, get a progression from that key and draw your melody notes from the chord's pentatonic. Or start with the melody, but, include all the steps of melody, harmony and rhythm.