As mentionned in the other answers, ear training is in a category of its own. I would advise you to start with humming major scales and using an ear training course or software. Usually the first exercise consist of discerning the lower note between two, which is exactly what you need. Then you'll be able to move a step up and try to recognise intervals, thus later being able to sing the forth or the seven of any pitch you hear.
There's a lot to learn but if your like me, you will find that ear training is one of the most fun part of musical training.
Start by humming the scale (don't bother so much to learn different keys at first). I say humming because you don't want to focus on your vocal technique at all and it should allow you to better hear both your voice and the scale.
Learn it up, then down, then up and down. Switch key. Then isolate each interval.
Start you major scale and stop at the second note - Root to major second : that's your first interval. Link it in your mind with the start of a melody you know. For the second, that
quite easy, lots of popular and traditional songs start with a major second. The one I personnaly use is Frère Jacques because I'm French, but you might use any one you like.
First to third note of the scale is your major third. I personnaly use a French song you wouldn't know (michel fugain Fais comme l'oiseau) but you might use When the saints go marching on.
4: Perfect Fourth : First two notes of Amazing Grace.
5: Perfect Fifth : First two notes of Star Wars theme.
6: Sixth : this one's trickier to find. I again use a French song, but you can use first two notes of verse of Angels by Robbie Williams. You could use first notes of Canvas Bags also. Or first two notes of My way.
7: Major Seventh : This interval is rarely played ascendingly. I use Somewhere Over the rainbow's first and THIRD note.
8: Octave : Somewhere over the rainbow first and second note :)
I gave you my example, but I think it's very important to use song YOU know well. Keep playing each interval ( with a virtual piano like this one if you don't play any instrument ) until a song you know pops up. I think it works better if you're very emotionnaly attach to this song (or one you know from your childhood).
Eventually, you would need to find songs for other "in-between" intervals (minors and flats) or to recognise intervals when played together. But before then, this workout should really help your so-called tone-deafness.
That might sounds like a lot of work but I promess it is actually really fun and rewarding.
If you struggle to find songs to associate, you shoud google "Interval song associations"