A couple of points.
1. 250 million years is a long time.
Ignoring heating from below, a spherical shell of rock the size Earth will cool from an arbitrarily high temperature to 300 K in a mere 30,000 years. (Aside: This is what led Lord Kelvin to erroneously estimate the age of the Earth to be no more than 100 million years.) This Kelvin cooling time scale is orders of magnitude smaller than cited figure of ~250 million years. The Earth had plenty of time to begin forming a significant temperature gradient in that time span.
2. The Earth did not have to cool to ~300 K.
It didn't even have to cool to 373 K (boiling point at 1 atmosphere). The primordial atmosphere was much denser than today's atmosphere. Some posit pressures as high as 150 atm based on the amount of CO2 sequestered in limestone and other mineral deposits. The boiling point at 150 atm is 344 C, or 617 K. This reduces the Kelvin cooling time even further.