I used to be in the same boat and was very frustrated by it as a child and young adult. Playing by ear comes down to training your brain to hear all of a piece of music, including what's not there but would fit nicely. An awful lot of people can only "hear" the melody, or the sopranos in the choir, or the famous guitar lick.

I've had about nine years of various music lessons but no formal ear training. So, the following advice is what I figured out myself, mostly in my thirties. It's geared a little more toward singing than playing, more toward arranging than original composing. You'll probably notice I don't have a terrific head for jazz. This advice shows my age (and my whiteness), but hey, sometimes old music is good music, sometimes old composers are good composers. Stand on the shoulders of giants, and all.

Advice (in approximate order of difficulty and creativity):

1) Give up air guitar. :-> You need to make your own noises.

2) Play and sing intervals and scales. Pick a note, any note, such as D. Start at D and jump up a 2nd, jump up a minor 3rd, jump up a major 3rd, etc. Jump down a 4th. Go up and down the major scale, the minor scale, the Spanish/Jewish scale, etc. Hum this stuff to yourself while you're driving or cooking or waiting to fall asleep. Also, hear these things in your head without making audible noise. You can work on your intervals and scales in your head while your significant other is asleep.

3) Sing the appropriate do-re-mi words to the notes of simple songs (major keys without accidentals). Listen to "Do-Re-Mi" from "The Sound of Music." I mean, the "do mi mi, mi so so" and "so do la fa mi do re" stuff toward the end. That's what you're going to do. For example, sing "Twinkle, twinkle, little star..." as "Do do so so la la so..." Your voice might be bad, but your brain is getting the hang of something new and interesting.

4) Play and sing chords. Pick a key, any key, such as D. Learn to play and hum the notes in the Dmaj, Dmin, Daug, Dsus, D6, D7, Dmaj7, D9, etc. chords. Hum broken chords as you go about your day, and work on them silently in your head when forced to sit through a PowerPoint presentation.

5) Hear, sing, and play bass lines. Listen to disco. I'm serious, listen to disco. A disco bass is prominent and follows nice patterns, and so this exercise is not too tough. Identify what the bass is doing and hum along, even if you need to do so one or two octaves higher. Memorize that bass line. Then play it on your piano. Play it in a different key if that's easier on your brain. Play it in different keys because that's hard on your brain. (Hint: "Funky Town" is much easier than "Disco Inferno," which is much easier than "You Should Be Dancing.") If you're having trouble with this, get a book of boogies and notice the patterns your left hand is playing. Then head back to those disco records. After disco, try the bass in other pop genres. It's usually not as loud and patternous, and sometimes it gets "lost" in power chords. Yes, "Day Tripper" and "Smoke on the Water" have famous bass licks, but the trick is hearing the bass throughout.

6) Hear, sing, and play vocal lines. Listen to the Everly Brothers, the Beatles, BeeGees, or some show tunes. Identify each voice in the recording and take turns singing along with the various voices, not just the melody or whatever vocal notes happen to be the highest. (Hearing the non-melody or the not-highest vocal can be especially tough.) Sit down at the piano and play those parts simultaneously. Graduate to barbershop quartet, doo-wop, the Beach Boys, and jazz vocal groups (Andrews Sisters, Pointer Sisters, Three Mo' Tenors, Manhattan Transfer, Take 6, etc.). Take a stab at someone like Rossini or Verdi (I find Puccini awfully hard to grok). You might have a lousy voice, or your playing might be awkward, but the point is your brain knows what's going on with all the vocals.

7) Imagine a given song done in a different style or time signature, even if all you can handle is the melody and you can only kind of, sort of imagine other parts and instruments. Examples: Neil Sedaka doing "Breaking Up Is Hard To Do" in two very different styles; "La Dona E Mobile" from "Rigoletto" (3/4 time) and the theme song from the "Lidia's Italy" cooking show (same melody in 4/4). Some years ago, I was singing something very bland in a choir, and I noticed my alto part was a doo-wop bass vocal sung an octave too high and in completely wrong rhythm. Oh, and it needed to be "Bubba da-boom, sha-boom..." instead of whatever my lyrics were. I spent the drive home imagining the whole shebang done as doo-wop, which helped me feel much better about that bland thing we were stuck with.

8) Hear the essential chord changes in recorded songs. Listen closely to folk, country, blues, early rock, Southern rock, or roots rock. These have a rather small number of essential chords, and they don't change all that often--even if a melody wanders all over, even if John and Paul are harmonizing all over, even if a guitar screams all over, even if Jerry Lee Lewis pounds keys all over. In fact, a few songs boil down to just one chord. If a song has acoustic guitar strumming, you're in luck because it's playing the essential chords, and you can easily hear when they change. Otherwise, listening to the bass comes in very handy: when the bass pattern changes, that's a chord change; when the bass hits a different low note, that's a different chord. You can verify the changes you're hearing by looking at printed music that shows the chords across the top.

9) Figure out the obvious chords that go with the simple songs you sang in kindergarten. I'm talking "Twinkle, Twinkle Little Star," "Jingle Bells," "The Hokey Pokey," "The Farmer in the Dell," and so on. Do this without listening to recordings. How? With a circle of fifths diagram. You know from listening to the songs in exercise 8 how often the chords are likely to change. So now the question is, just what are those chords? Pick a key, any key. Find it on the outside of the circle. These really simple Western songs in major keys always start with that chord, though not always on that note, "do," otherwise known as the tonic. "Twinkle" starts on the tonic (do), "Jingle" starts a third higher (mi), "Hokey" and "Farmer" start a fourth lower (so). Start hitting chords and singing along. When you sense a need for a chord change, head one or two steps clockwise or counter-clockwise around the outside of the circle. When you go up a fifth (the Wikipedia circle shows this as clockwise), you might want to play a 7th chord (minor 7th). When you go down a fifth (counter-clockwise) or return to your original chord, the basic chord will do (no 7th). Your chords on the diagram will remain very close to that first chord, and you will return to that first chord often. In fact, I guarantee you will end on it. These neighboring circle of fifths chords will sound "right" and obvious. You'll notice that rounds, such as "Three Blind Mice" and "Frere Jacques," don't have much going on. In slightly more advanced songs (off the top of my head, perhaps in the long "peace" in "Silent Night"), you will occasionally want to play the minor chord on the inside of the circle instead of the major chord on the outside.

10) Hear and identify the essential chords in recorded songs. Listen to those songs from exercise 8. Now you can hear the essential chords and identify them on the circle of fifths! Things get easier from now on. Play rhythmic chords with your right hand and the bass line with your left. As you play, sing the melody or invent a harmony. Now you're starting to cook. The fact that you're not playing all the notes you hear in the recording doesn't matter. What's important is, you're playing something that works. In fact, you can do a passable job in a garage band, especially if it has no bass player.

11) Listen to Christmas carols. Even if you're not a Christian--even if you're a hardcore Ayn Randian--listen to carols, especially the "religious" stuff from hymnals. The point is, you want to listen to a zillion different versions of the same ostensibly straightforward songs that have been around forever. Identify the essential chords you hear. Most versions use the "right" chords. (The Mormon Tabernacle Choir is "right.") Simon and Garfunkel's "Silent Night" is right but horrifying. A lot of versions are right-ish and funkified. Keep alert for versions which are "wrong" somehow. For example, Bruce Cockburn and Sam Phillips do an eerily wrong "It Came Upon a Midnight Clear" by changing the melody a bit and playing wrong chords. IIRC, it shows up in the WWII movie by the same name.

12) Play or sing one song (in a suitable key) while listening to a recording of a different song. Yes, it's doable, even if you need to do one of the songs a bit "wrong." This is called counterpoint, and it's something that used to amaze me when I was a little kid watching "The Carol Burnett Show." Steve Lawrence or someone would show up as a guest, and he and Carol would sing two different songs simultanously or interleaved. If you're too young to remember or can't get your hands on old Carol Burnett episodes, listen to "The Music Man," which contains several examples of counterpoint: "Lida Rose" with "Will I Ever Tell You?", "Seventy-six Trombones" with "Goodnight, My Someone," and "Pick a Little, Talk a Little" with "Goodnight, Ladies." For decades I wondered how anybody could possibly know which song fits with which. When my brain finally started hearing what chord progressions are suitable for what melodies, and how to be "wrong" but good, it became obvious. Oddly, I started out hearing U2 with other stuff, maybe because U2 is pretty simple. For example, if you zoom through "Bullet the Blue Sky" (with the shorter rap) it fits exactly into John Denver's "Wooden Indian." You can sing a wrongish rendition of "What a Friend We Have in Jesus" with "Love, Rescue Me." With some ingenuity, you can fit the Beatles' "A Day in the Life" (including the weird, climbing orchestra and the "ah"s) into "Numb" (then tack the giant piano chord onto the end). Etc. BTW, Collective Soul's "December" is almost the Doobie Brothers' "Black Water," and you can sort of sing Verdi's "Gloria all'Egitto" march in "Aida" to Richard Rogers' "How Do You Solve a Problem Like Maria?" wedding march in "The Sound of Music." Pretty soon, if you've heard one song, you've heard them all, and they're all interchangeable.

13) Call yourself a musician. Find the cool people in your town, and join or form a garage band. You can do a passable job by now, which means, yes, you are a musician. You want your bandmates to be better musicians than you so that you keep growing. How do you find cool people, decent musicians? Well, you can hang out in coffee houses. You can mingle at the receptions and after parties following smallish-venue concerts. You can bring your instrument or voice to jam sessions at bars. Here's the thing: when someone says "Are you a musican?" or "You must be a musician," always say "Yes," even if you feel like a lying dork. Saying yes to the right people opens amazing doors. I've wound up playing in garage bands, creating orignal music arrangements for churches, and performing opera. Just keep calling yourself a musician.

Sorry I got long-winded here. But your question got me pacing the floor, and I had fun writing my answer.