Is it true that oxygen has a diffusion rate in air 10,000 times greater than in water?
Yes, according to calculations presented here and here the conclusion is that:


  The O2 diffusion coefficient in saturated air (15% oxygen) is 5,700 to 10,800 times greater than in water (60°C and 20°C respectively). 


And here is a paper using this difference to investigate the transfer of O2 through the tracheal system of a click beetle.