As far as I understood, songs are played in keys.
Keys are one way of making sense of the harmony of a piece of music. They're a very common way, and often a useful way, but not always. Don't make the mistake of thinking that keys are absolutely fundamental to the way music works - they're simply one way of looking at things.
This essentially means that you pick a scale (let's say, C major) and you use notes of that scale. Chords can be built from notes that are in the key of C major. Notes of the C, G, Am and F chords for instance are all from the C major scale, thus a progression C-G-Am-F is also in the key of C major.
That's a good description of what would be a very simple 'beginner' way of creating harmony using the major/minor system. But of course, you're allowed to go outside of the notes in one key, and you're allowed to go outside the chords in one key...
. One can, however, also choose to play different scales over the different chords: G major (among others) could be played over the G chord, for instance. This scale, however, contains an F#. Does this mean that playing a G major scale over the G chord in the above progression moves part of the song out of the key of C major?
...which as you say, raises the interesting question - if you're going outside of the notes in one key, at what point does that mean that you're in a different key?
Ultimately, there aren't really any strict rules you can make. One person might consider a certain chord progression or melodic sequence of notes to constitute a key change; another might think that it's a borrowed chord, or feel that the piece was in a different key to begin with.
How can I possibly establish the key of a particular song?
Well, if there's officially-published sheet music that shows the key, then that's the key. Even then, you might want to argue that the way it has been notated isn't the best.
If a song has as many keys as chords, the concept of key looses any meaning.
Not really, because as I said at the start, a key isn't a fundamental part of the nature of a piece of music - it's simply a perspective from which you can look at the harmony. Sometimes it might be interesting and valuable to look at a part of a chord progression both from the perspective of considering that there has been a chord change, and from the perspective of considering that there hasn't.