I've been searching Google about this a lot but couldn't find a solution for it. For example, in the solo part of "Nothing Else Matters" where does the A# come from? I can understand why, for example, C# can be used in a E minor, even though E minor doesn't have that note, due to D Major having it in chord progression. Can someone please enlighten me about this. Thanks.
A♯ in e-minor is just a blue note. These are found all over rock music. Yes, it does not really fit in the key, classically speaking, but that can be used as a deliberate effect – it's a dissonance used to convey a somewhat painful emotion, or... whatever, you must know for yourself how you perceive it.
As Tim says, in principle you can use any note in any key. Just you should have a feeling what effect it incurs for the listener. Choosing only notes from the key's default scale makes sure that nothing will sound too jarring, but often it also won't be particularly interesting.
I suggest looking into 'non chord tones.' This will give you some music theory terminology which can be used to describe and label notes that don't 'fit' a given chord. The artful use of non chord tones adds expression to melodies. You find them in practically every style. Pop, classical, rock, etc.
If a chord in a measure (bar) does not have any notes that are less than four semitones (frets on one string) away from the melody notes then it often can be played without clashing with the melody. It may not make any harmonic sense but it will work.
Say you are playing in the key of D and you play a bar that consists of the melody notes E B D. You could play an Em7 (E-G-B-D) or an E7 (E-G#-B-D) chord in that bar. Why? Because in order for the G# in the E7 to clash with melody, the melody would have to have an F, F#, G, A, or Bb in it.
I used the length of a bar for simplicity but this applies to any duration of the melody notes and the chord.
Note that one way you can use a clashing note is if you put an octave or more of distance between the notes. C next to D is a clash but C above D is a dominant seventh.