Coldest I've ran in was about -40 with windchill and I froze the inside of my nose and got a nose bleed.
The coldest I can handle normally is about -30. You just have to wear a balaclava that protects your entire face. The warmth of your body heats the air before it hits your lungs.
Wear tights, wind briefs (if you ever want to have children), under layer, top layer, and maybe a jacket if that's how you roll, a balaclava, and a hat.
I usually put my hands underneath my sleeves and that works for me, but you might want gloves as well.
You can almost always run outside and if it's only occasionally below -25, it won't harm you. I know, because I've been doing it for ages.