I would suspect allergies. Especially with tummy and back leg licking.
It isn't easy pinning that down though. I'd start with the diet. Try to eliminate the main triggers. First, slowly switch to an all wet food diet and no dry. Dry by nature, is full of allergy triggers. Look for wet food that has meat as the first ingredient, no or low grains and doesn't
have: glutens, soy, corn, fish, chicken.
When my cat had the same problem, switching him to Wellness wet food (and some supplements) did the trick. There are also foods specifically formulated for allergies like Natural Balance: venison and pea.
I would also eliminate as many environmental triggers as possible, air fresheners, scented candles, smoke and caustic cleaners can be suspect.
For immediate relief, your vet could give your cat a cortisone injection. I'm actually surprised he/she didn't suggest tat already! It will not solve the problem but, if your kitty is in extreme discomfort, it's a quick, short term fix. However, I would avoid repeated or long term use.
Here's an article you may find helpful:
http://www.littlebigcat.com/index.php?a ... giesincats