Temperature scales are somewhat man made. We feel heat (cold = lack of heat) due to the kinetic energy of the molecules of air that hit our skin. Also, from school, I remember that absolute temperature is proportional to the kinetic energy. So, if we assume that twice as cold is half the heat then the kinetic energy has to halve also.
Lets employ some algebra ...
If the outside temperature is T0 degrees Celsius then the kinetic energy is E0 = k(T0 + 273) and half the kinetic energy is Ex = E0/2 = k(Tx - 273), where Tx is the temperature we're interested in and k is the constant of proportionality.
Thus,
E0/2 = Ex
or
(T0 + 273)/2 = (Tx + 273)
or
Tx = (T0 + 273)/2 - 273 = T0/2 + 273/2 - 273 = -136.5 degrees Celsius
I'd say that the answer is -136.6 Celsius
A quite silly answer for a fairly silly question
(p.s. thanks for giving this insomniac something to think about)