This has always puzzled me. Yesterday (in London) it started hailing despite it being about $20^oC$. A couple of years ago I experienced hail in Sicily when it was about $35^oC$ in the shade!. How is this possible?
Temperature generally gets cooler as you go higher in altitude (which is one reason why you have snow on mountain peaks long after it has melted away in the foothills).
Hail develops in thunderstorms. A thunderstorm ~BY DEFINITION~ is a storm which has developed through the freezing layer. So think about this: If you see lightning or hear thunder from a storm, you can be absolutely sure that at least part of that storm is above the freezing altitude, and at least part of the storm is below it. Thunderstorms often develop on warm days; and they also often develop on the edge of a cold front, where cold air is overtaking and riding over the less dense warmer air.
A typical thunderstorm case: It is a very warm day, and the air might be quite humid. The warm moist air tries to rise to get higher than the cooler drier (and therefore heavier) air above it. The moist air rises. As it rises it cools past its dew point and moisture droplets precipitate. These droplets can be blown up by the rising air, higher than the freezing altitude, where they freeze. They start falling through the moist air, freezing a layer of moisture onto the small iceball, then may be blown up again by updrafts. The process can repeat many times as the little iceball goes up and down past the freezing level, each time growing by adding another layer of frozen moisture.
Eventually the little iceball is too heavy for the updrafts to keep it aloft in the freezing zone, and it falls to earth as hail.