Best is of course subjective, but overall, given your question and caveats, I would say a good solid winter tent.
To elaborate on the alternatives, if you have an assured amount of snow, then you can attempt some form of snow shelter. Building an actual igloo takes quite a bit of practice. Building a snow cave on the other hand is not that difficult, but does need quite a pile of snow of the right texture. Given that you want this method to work on plain frozen ground then any kind of snow shelter is likely out.
Other temporary shelters, like lean-tos also largely depend upon the surrounding area for building materials. If you are in more open country, you may well lack the requisite branches/trees, in order to make this work. Also depending on where you camp, you might get in trouble for stripping live branches for your shelter, or to sleep on, so know your area.
Overall, therefore, a good solid winter-rated tent is probably your best bet. You'll know you have it with you, and even if you want to try out a snow shelter or other variation for one night, you'll have the tent to fall back on.
Good Luck