¿How do you tell if a person is vegetarian? Test the microbiota.
The population of microbies in the gut is a function of diet, drug treatments, etc.(See, for instance, this article.) The procedure would only require a stool sample, from where the DNA would be extracted and analysed.
Given the volumes you have to process, the whole procedure can be fully automated. The lab machines can fit in a few large rooms scattered around the city, and the data would be sent to central supercomputers (probably the most expensive part).
Note that you cannot fool this method by just eating some meat before getting tested, you actually have to incorporate it in your diet to affect the bacteria population.
As a bonus, for the same cost, you can make a good sampling of the population's health and catch early most of the colon cancers and other gut diseases.
(If you are interested in this approach, I can add more the details.)