You need to understand music theory. It's hard work, but it explains exactly the science behind music. To be honest, melody in traditional music normally goes over chords - but its perfectly possible to find melodies that work and the devise chords that fit - but for beginners it's harder because its easy to find three or four chords that work with the melody, BUT fight like mad against each other.
You need to understand chord numbering - once you do, the actual key of the song can be changed to anything you like.
When people start, the usually pick C Major because it's normally white notes. C=chord 1 - the rock or root. In historic music from VERY old to current, if you want an9other chord, chord 5 is useful, which is G, chord 4 F is good too. If you want another, then chord 6 works. There are thousands of popular songs using 1, 4, 5 and 6. The order you glue these together either works or it does not. THIS is the problem. To be a musician - a real one - requires your ear to hear the chord changes and say nice, I like that, or yuk - that's horrible. You may not at this stage have a melody at all, but your ear and brain reject or accept the chord changes. Music theory will explain why this happens. If you look at the actual notes in chords 4 and 5, you'll find they're not all 'white notes' so you've added in extras, you can stick in the melody - but ONLY at points where the chord allows. Simple melodies sound like songs from young kids at school. They're memorable, but not exciting.
If you try to create as a novice, melodies featuring all 12 available notes, without understanding the theory, you get a Jason Pollock painting, without Pollock's eye. Actually Art and painting has very similar mixing and quantity rules to music. Technique as well as vision is needed. A Lichtenstein piece vs Constable - different pallettes of colour - one limited in colour quantity, and no mixing or blending and the other with varying hues and saturation.
If you don't study music theory, you will, if musical, learn it accidentally because the things in your music that work NEED you to follow the rules - but you discovered the critical rules on your own. Music theory goes wrong with music that developed culturally independently - Asian music is a good one to listen to. Scales with missing notes, tunings that to our ears are odd, or plain wrong. No doubt somebody listening to Japanese music with no experience of European origin music would find ours very strange. Ours, I suppose, just has science built into its development. I often wonder if the notion that we have A as 440Hz was in fact not true for a very long period of time - and like 'railway time' was a gradual introduction to make systems work, and not anything magical.
If you study Bach and his tuning changes, you discover science again. It's hard going, but it explains so much. If you are a guitarist you tune your gear by ear by using harmonics and beating two notes together. When I had my first cheap guitars, we had no tuners and I'd tune so I could play along with records, on my record player running at 44 and a bit rotations a minute. My E wasn't E at all. Even worse, my guitar tuned by ear sounded ok when I was on Bert Weedon's book. Then I discovered Barre chords and could play Status Quo - BUT - my rubbish guitar played A at fret 5 out of tune - so I had to detune open E a bit, so both were nearly right. Bach had this problem hundreds of years ago. He wrote something on the tuned by ear piano, then tried to play the same melody in a different key and couldn't - it was out of tune. He worked out why, and fixed it by moving the 'perfect' tuning of the strings to a nearly perfect tuning - but enabled him to write music in any key. Clever fella.
You mentioned generating feelings. To me the thing here is Major and minor chords. A minor I always thinki is a sad chord and I like sad music and use it a lot. House of the Rising Sun - has the minor chord first. However, A minor has the same notes as C major - a happy key. That set of sad notes is exactly the same set of notes as the happy set? Music theory lets you understand what is happening.
When I write a melody, somewhere in my head, I'm imagining the chords. I don't think I every come up with a melody without something in my head saying chord? I suspect that if you are musical, so can create strings of notes that work together, you already have a grasp of music theory without realising it. To often peoploe who really understand it start to explain it with language that is confusing or impossible for others. All it does is explain why in general things work, and often don't. My colleague used to tick me off because I had a thing for melodies with a harmony under it spaced a 5th away. I liked it, he didn',t because consecutive 5ths are one of the 'rules'. However - music theory does give 'permission' for some things when two rules collide - which always happens and can be done on purpose for effect.
It's boring and it'd really dull to learn it to exam standard, but here in the UK, music theory to Grade 5 is blisteringly handy for song writers. Go above 5 and it starts to get VERY complex and totally unrelated to popular music. Instantly, this statement makes 'real' music people start to throw things and raise eyebrows - but I found going higher impossible for me, but what I learned up to Grade 5 was and still is everyday nuts and bolts stuff. One warning - the books are rubbish in general. A music teacher is bar far the best solution for music theory - cutting through the insignificant stuff and aiming at the critical.
