Why does air remain a mixture?
From your comments it seems that effectively you are asking about "why do gases mix so easily?"
If a system such as a mixture of gases is kept under constant temperature in a constant volume, the equilibrium state corresponds to the minimum of Helmholtz free energy:
$$A = U - TS$$
As you see, for $A$ to reach the minimum either the energy $U$ should decrease or the entropy $S$ should increase (or both in reality).
Minimizing energy. Most of the energy of common gases at normal conditions comes from their kinetic energy defined by the temperature. Energy due to intermolecular potential is negligible. So the only possibility to lower the energy is to lower the gravitational energy. In essence it would require the mixture to perfectly separate --- heavy gases at the bottom, light gases up.
Maximizing entropy Maximum entropy for the system in hand (under specified conditions) would imply perfect mixture, the state of most disorder. That's actually what drives the diffusion.
So as you see, the equilibrium state is a compromise between low energy and high entropy. For gases the entropy wins, because there isn't much energy difference between a mixture and a separated state (apart from gravity, which is still small).
As for your example with oil and water the situation is opposite. Unlike gases considerable amount of energy in liquids comes from intermolecular forces. Thus there is a huge differences in energy of interaction water-water or water-oil, so it is more preferable do separate to considerably minimize the energy.
CO2 will, on average, equilibrate slightly lower than O2 in a gravitational field. But the difference in the force of gravity is very small compared to the random thermal motion of the molecules, thus the effect is effectively negligible in day to day life.
In the context of the atmosphere as a whole this can be a non-negligible effect (e.g. this link), and in astrophysical contexts, this can be very important (e.g. this paper or this one).
The exhaled air is lighter, because it is hotter, and this swamps the CO2 density difference. But if you have pure CO2, it will fall down before diffusing into the air around it--- there is a common demonstration of pouring CO2 on a candle to snuff it out, you can do it as if you were pouring water, the CO2 displaces the oxygen and the candle dies.