So how does the ECU know it is bloody cold outside? Have you checked the ECT (temp sender for the engine and ignition computers)?

Assuming that is good, and you are getting no codes it time to go back to the basics:

Correctly timed, high energy spark
Sufficient, well atomized fuel
Sufficient compression

On the spark, all you can do is change tune-up parts like plugs, cap, rotor and wires IF you getting a nice fat blue spark at the plugs. Coils can fail but it is so rare, you have to eliminate about everything else first unless you have a compatible known-good spare.

On fuel, it is probably time to check the fuel pressure at the rail. It is unlikely but ice crystals in the fuel filter could cause a serious restriction. Honestly never seen it in a car but ice-clogged fuel strainers in aircraft have caused many an issue.

Compression is only likely to be an issue if you have a seriously blown head gasket or the timing belt jumped a few teeth. In that case, the car would have lots of other symptoms.

Of course there is always the infamous temp-related vac leak but that normally affects idle, not starting.