Level up moveset. And besides, even if you were going to waste all of your TMs on Gyarados, it wouldn't be helpful against Garchomp in particular, which is the whole reason I brought up Abomasnow. Besides Earthquake and Stone Edge, all of the usually great moves it can learn by TM are special moves, which don't leave a mark with Base 60 Sp.Atk.
Medicham will never outspeed Garchomp, and doesn't get STAB to any of the E4's main types. Floatzel has higher base speed than Garchomp, but without serious grinding to get Floatzel to Level ~63+ there is no way Floatzel outspeeds. It's a shame Medicham doesn't get Ice Shard.