For a gas like air, temperature is related to the spread in molecular velocities, not the average molecular velocity.

Wind feels cool due to convective heat transfer. In still air, your skin loses heat to the air a millimeter away, but that air is now a bit hotter itself, and it can transfer heat back to you. In a breeze, the air next to your skin is constantly replaced with new air at the average temperature of your environment. This is also why clothing keeps you warm-- it creates a barrier between the air next to your body and the air in the environment so they don't mix.