How did Old Time Brewers add Oxygen?

I don't doubt that oxygen is important to Lagers. I've been told that shaking the carboy is not enough oxygen for proper yeast health, that only pure oxygen does the trick....

If that is true, then how did they ever develop German Lagers, Bocks, etc that used to go into huge wooden vats? Not questioning the oxygen, just wondering how we got these styles correctly.

I would think oxygen was added "incidentally," either by diffusion from the headspace or by diffusion through the walls of the wooden vessels. Also,mthe wort was often times in broad, open "cool ships" that exposed large surface areas to the atmosphere.
In regards to shaking not being a effective oxygenation method I saw a video that explains that shaking is an effective oxygenation method, I even believe it was a Wyeast representative who states this.

http://www.wyeastlab.com/faqs.cfm?website=1#r44

Shaking will give you enough oxygen, it just takes work and you have the near certainty of adding some small number of undesirable yeasts and bacteria in the process. But if your pitching rates are adequite, the yeast will outcompete the nasties and you will usually have beer.