First of all,I'll list the major differences between these two:
Medicham-Mega: HP:60,Attack:100(200 after you count Pure Power),Defense:85,Special Attack:80,Special Defense: 85,Speed:100
Gallade-Mega:HP:68,Attack 165,Defense: 95,Special Attack: 65,Special Defense: 110,Speed:110.
As you can see above,Gallade is somewhat better than Medicham.It has more bulk and speed but is lacking in attack by a huge margin.
High Jump Kick: This one is probably Cham's signature move.It may be a bit risky but when it hits,it really PAYS OFF!!!
Fake Out: This one is great for disrupting the opponents strategy is used at the right time.
Swords Dance: Once you set this up,Gallade can be a HUGE threat.
Feint: Not sure if it is that useful but can come in handy if used at the right time.
I think Medicham wins this round.
Personally,I'd go with Gallade mainly because of the swords dance.Once it sets up,it covers up for the attack loss it has against Cham.But for it to be set up properly,it needs a follow me support which your team doesn't have apparently.So I would go with Cham with this moveset:
Medicham @ Medichamite
Ability: Pure Power
EVs: 252 Atk / 4 SpD / 252 Spe
- Ice Punch
- Fake Out
- High Jump Kick
- Psycho Cut
However,the final decision is up to you.
Hope I helped!