OLE SPROULS GUESS COULD BE CHICKEN/BEEF IN DOG FOOD.labs are prone to this in food. but you said you tried food change.
labs can take lamb in food but not much else.
toby can eat chicken but i saw labs that could not.

there is forum that could help you.i think it is called

www.woodhavenlabs.com go to ARTICLE section on top right.food allergies 1,2,3

this person is best on labs i have seen .drop her a PM ,she will help you out.

there is a disorder that labs or high energy dogs get. its from lack of mental and physical challenge and excercise. My lab had the same symtoms for a while and I really had to work him hard, let him sleep in our room so I could listen for him to start licking, and spend a good bit more time with him to get him to stop. Vet said sometimes you can sometimes you cant. It's called acute---- something. Your Vet should know what it is... if they don't get a new Vet.

i have seen that work and cheap too.but something is causing it.toby had fleas on top of his tail and he bit that area until i got k-9 stuff.no biting now.
labs are prone too things in their food,i see a lot of that.

that thyroid thing doc e said, seen that too.bad hips etc, seen that.my sisters dog chews her feet raw. vet said it was flea bite that did it.
that was year ago and dog is still biting hair off her food.