The question, as I interpret it, is about the conservation of energy during Joule-Thomson expansion. (That is, expansion of a gas through a small hole or porous plug, where there is a pressure difference between the two sides, and no work or heat is exchanged with the environment, except for work associated with the pressure change.)
Consider the classic Joule-Thompson experiment, where gas in a pipe is forced through a porous plug. Let the pressure on one side be $p_1$ and the pressure on the other side by $p_2 < p_1$, so that the gas flows from side 1 to side 2.
Now consider the passage of a small amount of gas from one side to the other. On side 1, the rest of the gas does work $p_1 V_1$ to push the packet of gas through the plug (where $V_1$ is the volume that the packet of gas has at pressure $p_1$). As the packet comes out of the other side of the plug it must displace a volume $V_2$ of gas, doing work $p_2 V_2$. In your car tyre, example, $p_2 V_2$ is the work the outflowing gas does in lifting the atmosphere.
In general, for real gases, $p_1 V_1$ will not equal $p_2 V_2$, for the reasons explained in John Rennie's answer. It can be greater or lesser, depending on the properties of the gas and on the two pressures. This means that the energy lost as work on side 1 will not equal the energy gained as work on side 2. This energy change must be compensated in order to satisfy the first law. Since the gas can exchange neither heat nor work with its surroundings, the only other thing that can change is its internal energy. The first law implies that $U_2 - U_1 = p_1V_1 - p_2V_2$, as Wikipedia explains.
It happens that for most gases at room temperature, $p_2V_2>p_1V_1$, which implies that the gas's internal energy (and therefore its temperature) must decrease as it goes through the plug.
Note that we didn't assume the entropy stays constant, and in fact it increases: the entropy change associated with expanding the gas must be greater than the entropy change associated with reducing its temperature, otherwise the gas would not flow through the plug.
In your car tyre example, the gas does indeed to work in lifting the atmosphere, but this is less than the work done by the gas inside the tyre forcing it out through the valve, and this is why the temperature has to decrease.