Forgot to mention that she never comes close to making them bleed though. I would definitely try to break that habit before it becomes ingrained, since he takes it to an extreme. Bitter tasting but safe substances on the feet may work, or Velcro dog booties which you can buy or make (check out dog carting and dog sledding forums for patterns). Some dogs don't do much of anything when their owners are gone (is. We have a backyard, but if our little girl is out back alone, she just waits by the door...first month of having her, we took her camping in a huge forest...someone left the zipper flap open and we was sure she was gone forever, but all night rather than run wild, she waited patiently for us to wake up right outside the tent door), so check for signs of separation anxiety. Finding out what is triggering what kind of anxiety will be helpful..or seeing if it is anxiety at all. Finding things or making things like puzzle feeders can help. Our dog bonded strongly to our cat, and curls up with her when we work, so sometimes another pet can help. Sometimes it makes things worse. Bones that take a long time to chew, or finding other forms of stimulation while you are gone can help. When home, some dogs feel tops when learning tricks, some being brushed, some playing a game of ball, but there is probably something your dog loves doing with you, so make sure you schedule in some dog time each day. If deep seated and unresponsive anxiety is proven to be the cause, some homeopathic, herbal, and medicinal treatments exist. These things should hopefully help.
I wouldn't rule out irritation of the nail beds or feet though, since the chewing is so focused.
