Well, it's not quite true to say "Each song is played in ONE specific key". It's not at all unusual for a tune to temporarily change to a different key, and a lot of pop songs change key towards the end and then stay in the new key.
Next, a key isn't really a combination of sharps and flats. Rather, it's a starting note and a scale built on that note. C major and A (natural) minor have the same set of sharps and flats (none!), but are different "keys". Because you are starting on different notes, the pattern of tones and semitones is different so the scale is different.
If you got to 24 keys because of 12 minor and 12 major keys, you have a whole world of modes yet to discover. Using just the white notes on a piano - no sharps or flats - you don't have to start on C (for major) or A (for natural minor). There are seven notes you can start on, each giving you a different scale, and each with its own name. Starting on D (which gives you a key called the Dorian) or G (Mixolydian) is common in Western folk music. Other starting places have other uses. And that's before we even start thinking about different patterns of intervals in the scale, such as we might find in jazz or world music (and the melodic minor, which "tweaks" the natural minor for musical convenience). It doesn't help that people tend to be sloppy with naming, and say a piece in D Dorian is in C just because it has no sharps or flats.
I think that's where your problem with the C natural minor comes from. If you start on A - not C - with no sharps or flats, you get a natural minor scale, but it's A natural minor, not C natural minor. To get to C natural minor, you have to shift the pattern of tones and semitones to start on C, not A. It turns out that gives you the same notes - the same set of flats - as Eb major. It's not Eb major, though, because the tonal centre is C.
So the answer to "are a key and scale even related to one another?" is yes, they are, but it's very far from a simple one-to-one relationship.