Did you get kicked out of the school? I mean, I can't figure how this could be impossible ... I saw so many people I would qualify of tone deaf who finally could manage taking some simple melodies. You just have to practice to learn how the different intervals sound. You begin with thirds fourth fifths and then go on and finally you have every interval. Then you learn how they work together and you don't even have to ask yourself about wich intervals they make, simply how do they all relate to tonality/harmony.
LOL, no, I think I managed to make up for it with my good sense of rhythm. And perfect attendance.
I do just fine if you set a cadence for the key and then present a pitch, or telling the interval between two notes at the same time (50% chance here, because I usually mistake an interval for its inversion ie. same notes). Melody is the hardest, but it shouldn't be so hard if we were allowed instruments, no? I mean, I can pick out Happy Birthday on a guitar, sure.

Maybe it's also a matter of perspective, but for me, you'd have to have near perfect pitch to do it without an instrument. Most people I know are really tone deaf, worse than I am. Lately, I've heard someone sing ALONG to the radio and still be far from the truth. Now THAT is tone deaf. I'm not THAT bad.
I'm not what you mean by just learning all intervals. And then how they work together so that you don't even have to ask about the intervals they make. But I may have tried that at some point in my desperation of last year. We were taught all melodic intervals, sure, but it did not help anyone who had to be taught. As for sense of pitch, I can honestly say nobody learned it at school. Technique, theory and sight reading, yes. Ear training, no.
It's easy to say, "oh, just learn all intervals" or "study all the pitches" but there's no proven method for this that would make just about anyone be able to pick out melodies/ harmonies without an instrument. Unless there be such method, I find that the existence of a subject as "ear STRAINING" is just unfair and a waste of time. I burned so many hours and shed so much tears on the subject for nothing.