
dont think this is a normal thing in dogs, certainly none of mine have ever had a foot smell! it sounds like a skin problem, an allergy or fungal infection possibly, maybe related to his ears? i would ask his vet to check them out, maybe do a skin scrape or pluck. they should also be able to advise a good shampoo as well.
with regards to the scratching is he treated for fleas? they are the most common cause of itchy skin.