Why do humans require vitamin B12 supplementation while herbivores do not?
The bacteria in the foregut of cud chewing animals (e.g. cows) provide enough B12 and other B vitamins. Uptake of B12 happens mainly in the small intestine. There are lots of bacteria in the human intestine but most fermentation of plant matter happens in the hindgut. 

Hindgut fermentation also produces B12 but since this happens past the small intestine it is not sufficient to provide enough B12. Therefore non foregut fermenting herbivores (e.g. rabbits) get their B12 when they consume their own feces, which they do anyway to obtain higher digestion efficiency of plant matter. I would not recommend this process to any vegan human though. 

As mentioned by bonCodigo, these animals need to take up enough cobalt, and their requirements for this element are higher than our own. 

Source:
Contributions of Microbes in Vertebrate Gastrointestinal Tract to Production and Conservation of Nutrients
C. EDWARD STEVENS , IAN D. HUME
Physiological Reviews Published 1 April 1998 Vol. 78 no. 2, 393-427