What rate of deforestation would be needed until we run out of oxygen?
As Jan points out, there are many other factors in the oxygen balance, not just trees. But for a bit of fun, let us suppose that we burn all the trees on the planet. The global biomass of carbon is estimated as 47.4 PgC (it varies a bit according to season and inter-annual growth conditions). Of this we can estimate that the contribution from trees is about 36.3 PgC. 1 tonne of carbon consumes 2.67 tonnes of oxygen to create CO2, so the oxygen consumed is about 9.68 x 10^^10 tonnes. The total mass of the atmosphere is known to be 5.15 Petatonnes, of which oxygen is 20.95%, or 1.08 Petatonnes of oxygen. So taking the ratio, the loss of atmospheric oxygen from burning all the trees is 0.0034%. This is far less than the day-to-day fluctuations in available oxygen due to changes in atmospheric pressure - i.e. the weather. 

So, there is a lot of woody biomass, but think of the partial pressure of the oxygen layer that wraps the Earth: 21.2 kPa O2 on every square centimetre of the Earth's surface. We are never going to run out of oxygen! On the other hand, pyrolysis of every tree on the planet would create so much smoke that we would probably all die of lung cancer!