I wouldn't say water is naturally cooler than air. What I would say is that water has a higher heat capacity than air. This means it takes more energy to affect the same increase in temperature and conversely it takes water longer to cool down than air. You can see this at night near bodies of water when the sea breeze changes to a land breeze as the land becomes cooler than the water - water temperatures tend to be stable across diurnal cycles.
I would also contest the statement that water cools the air. Water does both heating and cooling. When water evaporates into air, the air cools. However take a look at any thunderstorm you see -- that is water causing heating as it condenses and freezes. Water on the surface can also contribute to both heating and cooling. During the day the cool water surface will have a heat flux that cools the air while at night the opposite may be true. This depends on the air temperature and the SST.
Now on to your question, yes, there would still be wind if there were no water. The energy that drives the wind is differential solar heating at the earths surface. Variations in the surface topography and the shape of the earth mean that the solar flux isn't constant across the earth. As long as we have a sun we will have surface pressure differences and wind. Without water we would also see a stronger equator-to-pole temperature gradient (look at temperature variations right now on continents versus open ocean). This would result in stronger winds that we see today.