What if they built a building or found a cave where wind ran over a bucket or pool of water, cooling the air?
http://en.wikipedia.org/wiki/Evaporative_cooler#Physical_principles
"Water produces cold" is a plausible hypothesis for someone using Earth/Air/Water/Fire chemistry.
This thread is for discussing anything that doesn't seem to deserve its own post.
If the resulting discussion becomes impractical to continue here, it means the topic is a promising candidate for its own thread.