I am curious if you have experimented with the following:

1. increase iodine intake in some fashion

2. cut out all wheat products including whole grain

3. Atkins-style diet with restricted carbs in general

4. increased use of ginger as a spice or in tea (some believe it helps increase metabolic rate).

5. high intensity interval training (you mention exercise).