Seeing as he's my favorite mega, Gallade is actually a Pokemon I've used in singles/OU! Others have already covered his best sets, with Justified, a Jolly nature, and max Atk/Spd with Swords Dance, Close Combat, and then two of Psycho Cut/Zen Headbutt, Knock Off, Ice Punch, Stone Edge, and Shadow Sneak generally being the way to go (personally I ran Zen Headbutt and Shadow Sneak, but it definitely depends on your team composition).
Now, as for VGC/doubles...
Gallade was the mega I used on the first team that had great success in VGC 2015, and although he has a LOT of big issues (common Intimidates, burns, paralysis, Talonflame, Salamence after mega-evolving, Trick Room, Gardevoir and especially Sylveon, etc.), he also performs very well with the right support. Here's the set I ended up with in VGC 2015 that should still be fairly relevant for smogon doubles or Battle Spot doubles:
Gallade @ Galladite
Ability: Justified
Level: 50
EVs: 252 Atk / 4 Def / 252 Spe
Jolly Nature
- Psycho Cut
- Wide Guard
- Close Combat
- Protect
Justified can let you get a free +1 if you switch in on a Knock Off, as Steadfast is really pretty useless since you'll mega evolve him. Inner Focus is actually pretty decent in doubles as it will allow you to shake off Fake Outs and ignore Rock Slides from faster opponents. Jolly nature with this EV spread is pretty self-explanatory, as it allows Gallade to fully maximize his great base 110 speed after mega-evolving and his incredible base 165 attack. Protect is absolutely necessary for him to get the speed boost (especially if facing a fast Kangaskhan or one that has already mega-evolved), plus it's the best move in doubles. Close Combat destroys so many things. Psycho Cut is a good secondary STAB, but you can play around with this moveslot depending on what the team needs (Knock Off and Ice Punch will generally be the only ones you should consider, as something like Leaf Blade, Rock Slide/Stone Edge, or Thunder Punch will really only be for 1-2 specific targets). You can consider Zen Headbutt over Psycho Cut, but I've found this to be vastly inferior. The accuracy isn't perfect for starters, but many things that are weak to psychic moves (like Amoongus and M-Venusaur) are EV-trained to live a Zen Headbutt from the stronger M-Metagross, meaning yours won't OHKO either. While Zen Headbutt does have a chance to flinch, it is only a 20% chance, not 30% like Rock Slide or Iron Head (and it's single target, unlike Rock Slide). It's better to have the perfect accuracy with a higher chance to crit (which WILL get you the OHKO on those psychic-weak things, and helps you work around Intimidate). The last move is something I played around with a lot. Another attack is perfectly fine, but since burns and paralysis really cripple Gallade (due to his mediocre bulk he really becomes useless), I found that a support move in the last slot actually is best for him. Wide Guard became my favorite, as it still gives him usefulness against many of the common threats that will be thrown at him, but it can be fun to play around with something like Skill Swap.
M-Gallade has a lot of potential teammates that work well, but I feel like Bisharp is so perfect for him that he deserves a mention. Defiant wards off Intimidates against Gallade, and Iron Head and Knock Off destroy many of the common threats against Gallade. Gallade in return can eliminate threats like M-Kang and Terrakion, while also protecting Bisharp from many common spread moves that threaten it like Hyper Voice, Heat Wave, and especially Earthquake with Wide Guard.
Gallade in VGC 2016 deserves a mention, but unfortunately it's effectiveness has been greatly diminished. While burns are much rarer and paralysis isn't as common unless you see a Thundurus or Raichu, new threats like M-Rayquaza and Xerneas absolutely destroy it, Intimidate is still common, and Talonflame, M-Mence, and Trick Room are even more popular than last year. Gallade can probably afford to sacrifice some speed this year for bulk, as it may only need to outspeed M-Kangaskhan or at least the primals. Protect and Close Combat are still musts, but Gallade can utilize more of the tricks in his deep movepool this year. Skill Swap can be very helpful to control the weather, while Magic Coat surprises Smeargle and gives you a ton of momentum (especially since you can't flinch from Fake Out). Wide Guard still deserves a huge mention with all the massive spread moves. Quick Guard is useful as well, and moves like Thunder Wave, Destiny Bond, Snatch, Disable, Encore, and Ally Switch may have some niche uses if you really want to get creative. Gallade is far from the best mega in VGC 2016, and you may need to ask yourself why you're using it over another support Pokemon, but it may still have its uses with the right support and team composition (likely on a dual-mega team).