Weak to Water, Fighting, Ground, and Fire. Hmm, all of which Heatran is weak to (except Fire --> 4x Ground), yet he somehow manages to top OU. He doesn't have a single 4x weakness, which is great, and he resists Bug, Dark, Dragon, Flying, Ghost, Normal, Psychic, Rock, and Steel. He is also immune to Electric and Poison. Of course he would lose to a set up sweeper who already has a boost, most Pokemon weak to attacks would. Lucario and Gyarados have no business switching into this thing in the first place, as Earthquake / Rock-move would destroy them, respectively.
In Trick Room, he has the obvious advantage of resisting Bullet Punch. Besides, he is likely to learn Rock Polish anyways. Rock Polish / Earthquake / Iron Head (or whatever) / Stone Edge could work.