If you can make torterra fast enough, it could probably beat Gechamp. Gengar exploits TSS in hand and powers; Torterra plays more pokemon than TSS and uses alot of bodies instead of powers.
Machamp KOs basics, but a Torterra deck is built around evolutions, and if you're not able to evolve in a Tort deck, you've pretty much lost the game anyway.
That's one way to go, or shuppet works too, exploiting weaknes. Of course, that just gives gengar an extra 120 dmg when the pluspowers go back to your hand. If you made it a shuppet/Gengar deck, gengar would have to spend 2 turns shadow rooming your gengar or ohko it and risk the fainting spell. You could do Shuppet/jumpluff to give it permanent smokescreen effect.
Toxicroak G w/Weavile tech could also give gengar problems (As toxicroak already beats machamp 90% of the time)