Based on the two previous answers, this is my attempt from a microscopical point of view:
The portion of air that happens to be near the valve acts as a "wall". The rest of the air inside the tyre "pushes" this wall out. Thus, particles inside the tyre cool down because they are transferring Kinetic Energy to the particles in the wall. Adiabatic expansion
The particles near the valve eventually escape the tyre, so the energy that has been transfered to them also exists the tyre. Joule effect
Thus the Kinetic Energy of the particles inside the tyre gets lower and lower $\Rightarrow$ lower temperature.
(Example 6.10 from Fundamentals of Engineering Theormodynamics by Moran)
Edit: given that the particles of the gas interact (they "push" each other...) this implicitly asumes a Real Gas (not Ideal)