Regarding the larger question, the key for a song is more about the tonal center than it is about fitting into a pattern of notes (a scale).
Like so many things in music, a tonal center is mostly about feel. Also like so many things in music (theory), we can make decent predictions about feel, so there are mechanical ways to find tonal centers, but they aren't 100% reliable, and should be confirmed by feel as well.
It also might help to realize that some pieces of music have very weak or even non-existent tonal centers. In these cases, neither going by feel or theory will really answer the question, and then the larger question of what key it's in might be unanswerable, but also doesn't matter very much.
As an example of a piece that has a fairly strong tonal center that is possible to feel and determine by theory, we can go right to your example, The House of the Rising Sun. Listen to it without thinking too much but feeling instead, and feel for the "landing" place. For the vast majority of humans, it will feel like it "lands" or "comes home" right at the end of the first verse when the lyrics are "...house/of the ri-sing sun."
I put "sun" in bold because that's the actual landing site. Everything leads up to that word and note and chord. That's an A minor chord right there, so our feeling is that the song is in A minor. Now if we apply theory, and look at the chords, we will see that at that point the chords go Am - E - Am. That's a pretty solid perfect authentic cadence, which is just fancy talk for a "three point landing" in music. It's not just a landing, it's a solid landing, that leaves little doubt about whether it was a landing or not. Again, theory says, "Hey, we just touched down in the key of A minor."
For an example of a piece without much of a tonal center, I direct your attention (and possibly considerable patience), towards a selection from Musica Ricercata by Gyorgi Ligeti (made (in)famous by its use in the movie Eyes Wide Shut):
György Ligeti: Musica Ricercata II: Mesto, Rigido e Cerimonale
There are only three or four different notes played in the selection (in different octaves), and that's not a lot of material to get either a feeling or theoretical basis for a tonal center. If the notes used had an interval of a fifth, we might be able to make a case for the note that is a fifth below the other note being a tonal center. Instead the most commonly played notes form the interval of a minor second. Which means either could be an upper or lower leading tone of the other, although in context they don't really work that way. It's minimalist, maybe a bit impressionistic, and it defies traditional theoretical analysis. It does evoke emotion (in most people), so it's certainly valid music even though it defies the type of analysis we are used to doing.
To me that's a good lesson in why we can't get too bogged down in the theory. The theory doesn't drive the music. The theory just comes afterwards and tries to rationalize it, or even explain it. But it's not about theory, and sometimes it's not important to know what key a piece is in.