I have the exact opposite problem: I can only play by ear. Actually for me it's not a problem because the kind of thing I play (rock / pop guitar) is generally played by ear anyway.
One axiom which helped me enormously when starting on this journey (given I was new to music generally):
- The notes are all on the instrument somewhere!
Your'e already aware of that, of course, but for one given note there are only 12 others to choose from before the pattern repeats (per octave) so choosing the next note for a melody is kind of a limited choice.
When I started learning guitar, I found a song or two where the chords are picked on the strings individually. Using a bit of logic like "They played it on a guitar, ands it's a simple song, so the notes are on here somewhere and they're easy to find", I managed to find what was being played, and picked out the basics of a chord. To play other chords, I applied the same thing just at a different starting point. On guitar, moving a chord about is easy: Just move your starting point up/down the fret until it's changed the right amount. (That assumes no open strings). To play other chord shapes, find the same sequence of notes but starting on another string.
Then there's the melody: I think the answer from thatweirdpandanextdoor covers that very well so I shan't add to it.
For gluing it all together, I found a few other tunes which have 'known obvious intervals' (having sussed them on guitar) which if I hum the tune to myself, I know this part is a 5th or that part is a minor 3rd, or whatever. It's then possible to compare that to a song I'm trying to learn to see any similarities.
I've managed to learn popular tunes, some quite intricate, and improvise quite successfully without paying much attention to music theory. It's more that I've established for myself a system of how things seem to fit together, then I look at places like the magnificent StackExchange and find that others have already sussed it all out and have got names for it. I guess that won't be the same for you as you can already read music (which, from my point of view, seems like an amazing skill).
Finally: I can understand your frustraton. Learning to play (by ear) such that I can fumble a tune out without much/any practice was probably the best thing I've ever done- I hope it works out well for you !