Verkhoyansk and Oymyakon seem to be the coldest permanently inhabited places on earth.
Yakutsk the coldest city with at least 100,000 inhabitants.
now if we consider "major" cities with at least 1,000,000 inhabitants then probably it is the capital of Mongolia, Ulan Bator.
It is colder than Harbin and others.