I was able to gain 10lbs of lean mass in 6 weeks following the stronglifts.com program, and learning proper barbell form from Mark Rippetoe. I've been eating about 3500-4000 calories a day, with about 1200 of that coming from milk and the rest from meat, eggs, cheese, fruit, roots/tubers every other day, and vegetables. I was able to gain weight without gaining any fat.
There is a beast of a man inside you waiting to be freed. Work your ass off in the gym and eat a ton- especially a ton of animal flesh.
Of course, the problem with barbell training is the fact that you must know what you're doing otherwise injury is likely. But learn it, and you will get results much faster than using machines, dumbells, etc.