This is my method:
I play the melody and exclude all the keys that don't match. For instance, say the song is "I Need Thee", and the singer sings
I C
Need E
Thee C
How F
I Nee.. E
..eed Thee D
Then I know that C, D, E and F are part of the scale of the key we're in. Out of the 12 possibilities, only 2 contain all these notes: C and F. So, by now I know that we'll be in one of those two keys.
After this, I either play both chords (Cmajor and Fmajor) and decide the key or, more often, the key just 'jumps' at me by the placement of my hands.
But note how, by simply playing four notes, the choice has been reduced from 12 to 2.
For this method to work, you have to be able to 'see' patterns on your keyboard without thinking. This is achieved by practicing scales. If you know your scales and your chords your hands will simply 'fall' into the right position without a thought.
So, my advice to find the key you're in: practice scales.