Ok, basically you just have to experiment and find the root notes for the song. Like you said, the key is usually the first and last chords/notes in the song/solo, but it doesn't have to be.
However, if you can figure out the chords of the progression then you can figure out which key it's in, because certain notes go with certain keys. This is where the circle of fifths comes in. For example, if you know that the key of F has one flat, B flat, then you'll know that the progression - Dm, C, Bb, Am - is in the key of F. The Bb is the only flat note present in all those chords, so it has to be key of F.
On to the scales - you said that you know all the scales. I'm assuming that means that you know the patterns (i.e. the pattern of whole and half steps that BadHorsie mentioned). The relation between all the scales (mixo, minor, lydian, all that) is that each mode is built upon and resolves to a note in the major scale.
You know chord inversions? A regular D chord is D,F#,A - 1,3,5. A D chord 1st inversion is F#,A,D - 3,5,1. All that? Well, the modes are basically the same thing, inversions of the major scale. Here goes -
1 D Major
-whole step
2 E Dorian
-whole step
3 F# Phrygian
-half step
4 G Lydian
-whole step
5 A Mixolydian
-whole step
6 B Minor
-whole step
7 Db Locrian
-half step
8 D Major again
That's basically it. For instance, when you play Em Dorian, you're really playing through the D Major scale from E note to E note.
Hopes that helps.
