Try to do a little of both.Add a LITTLE more food to your diet,like a granola bar before working out,then go and lift weights/use an elliptical.I prefer the elliptical as it can give you both a leg,upper body,and arm workout at the same time.But it will make you tired as fuck fast.
For gaining strength and loosing weight this is perfect because the extra calories you eat are burned in your weightlifting so you can continue with loosing weight, but gaining mass and loosing fat at the same time is very slow and hard to do. I'd recommend that he does a clean bulk: 300-400 calorie surplus. It's slower than eating 700-800 calories over your BMR but you gain more lean mass. Also measure your BF% before bulking, the scale means nothing because you could gain back most of your lost weight but 1/6 of the BF.
Also read some of the bodybuilding.com forum stickies. Take all the advice except all the supplement crap and advice on what workouts to do (some recommend workouts that are clearly designed around advanced body builders). The only supplement you should be taking is protein and if you think your old enough for it, creatine.