I thought that this was an incredible and almost impossible feat, but I should have known better given that so many people have gone down this road. I gave it a try with my banjo, starting with "old McDonald" and Clementine. I find that my ear works perfectly well and I can immediately tell if I have the right note or not.
Also, there are not a myriad of possibilities. Most songs aren't played "down the neck" and a key only has 7 notes, so you don't need to try every possible fret. I does help to know the "fretboard" as they say -- and once you know to skip a fret in all cases except the jumps from B to C and E to F you are in good shape. Also bear in mind the key of G major uses F# not F -- it won't sound right if you run thru "do re mi" starting with G and then use plain old F.
There are great benefits to doing this. You can write down melodies as FFGBBA and such, but you really don't want to write anything down. You want to train you mind to work from "imagined sounds" to picking and fretting strings to make them.
Chords are something else, and I am ignoring them for the time being. What you don't want to make yourself is a machine for reading tab and then picking and fretting.
So far I have cheated by using tab or music notation to find out what the first note is for the melodies I have worked with.
Tony Trischka says that the first tune he figured out and played on his banjo was the "ode to joy". I know this well and have tried it myself. It is trickier that "old McDonald", but not at all impossible. It is D major when part of Beethovens 9th symphony, but is often converted to C major, which as no sharps or flats. So far I have picked it out using whole notes without problem. The first note is "B".