Meat/dairy is not the only source of B12. In fact, animals do not even produce B12. Certain microorganisms found in soil and the intestinal tract of animals produce B12. The intestines then absorbe the B12 into the flesh for use in the body. Some people even have the right bacteria to produce their own B12 but it is apparently not sufficient to prevent B12 deficiency in most people.(1)
B12 production requires Cobalt (thus the "cobal" in its scientific name Cyanocobalamin)(2) so the presence of B12 producing microogranisms in the intestines may be linked to adequate cobalt in the diet.
There are vegetarians in India who actually have sufficient quantities of the right bacteria in their intestines to produce sufficient quantities of B12 for survival.(3)
The body has the ability to store B12 for future use. People who recently became vegan but ate meat previously often have a large reserve of B12. However, inadequate supply of B12 can cause serious health problems so it is not recommended to rely on this fact.
The quantity of B12 required (2.4mcg) is so little that you could feasibly get your required amount by just eating some good soil or by not washing your (hopefully organic) vegetables. However, there is a pretty severe trade-off with eating dirt since there can be other things in soil that you might NOT want to ingest such as anthrax, leprosy, cholera and other not so friendly microorganisms. For now I will just continue to eat my fortified nutritional yeast.
Organic farming and soil building techniques have been proven to increase the presence of B12 producing microorganisms and these vegetables have been shown to absorb some of the B12.(4) It is not clear if this would be sufficient to survive on but it would be a step up from eating dirt.
References
(1) Albert MJ, Mathan VI, Baker SJ. Vitamin B12 synthesis by human small intestinal bacteria. Nature 1980; 283: 781-782
(2) SOLSTICE magazine #34, Feb. '90 (http://www.sare.org/htdocs/hypermail/html-home/8-html/0278.html)
(3)http://www.mercola.com/2002/jan/30/vitamin_b12_a.htm
(4) Plant and Soil 167:305-311, 1994. Southern Medical Journal 84(1):4-10, 1991.