The first thing I would recommend is not using BMI to determine whether you are over or under weight. Instead go by body fat composition.
That said, in order to gain weight, and not be fat you'll need to do a couple things:
- Eat some fat and carbs. I'm not telling you to go nuts, but this is going to help get more weight on. (more on the later)
- Build muscle. I'm not saying be a body builder, but you want to increase your lean mass to keep your body fat low as you gain weight.
If you are a guy, 10% body fat will give you a six pack and 15% will be a fit look.
If you are a woman, it will be higher (something like 23-28%)
Since you are on a very low fat, low carb diet, your body probably doesn't know what to do with that type of food. Be careful with re-introducing them. There's a couple strategies to do it:
- In the AM meal, incorporate grain carbs, fruit carbs, dairy fat/carbs along with your protein. I don't have my guidelines handy, but one serving each at the most. Do this for two weeks. After that, you can have some carbs with your dinner and fats with your lunch.
- or you can add one serving of one type of carb each day. Introduce a new one each week until you have all the sources covered.
Lastly, I shouldn't have to tell you this, but you still want a good amount of protein. At least 1g of protein per pound of lean body mass while you want to gain muscle. Of course with the extra protein, drink lots of water.
Finally, the exercise you choose is up to you, but you won't build bigger muscles (getting heavier while not getting fat) without demanding more of them. Some options are:
- strength training (obvious one here)
- swiming (excellent full body workout and cardio all in one)
- running
- climbing
The idea here is to demand more of your muscles so you can build them up, and feed them protein so they can increase.