"Bein" here doesn't means "leg", but "Gebein", that is, "bone" (note how similar the English word is to the German word). So "es friert Stein und Bein" means "it's so cold that it gets even into stones and bones" (the hard parts of nature, and the hard parts of a human). There are many such pairs that are traditionally used together, "gut und gern", "Haus und Hof", and lots more. "Ende (vom) Gelände" is different, that's a modern phrase and not a pair.

It means "extremely cold" Don't think much about the literal meaning. It's just a rhyme-play like "Ende vom Gelaende"