Same way any deck would deal with a Goth/Reun deck or a RossDeck. Go for OHKOs, outspeed, or find ways to disrupt by dragging up your Reuniclus/Vileplume with something like SludgeDrag(Muk UD) or Carnivine/Bellsprout's first attack.
If I'm playing Durant, I'd just keep milling.
If I'm playing Chandelure, I'd just drop 6 damage counters a turn and not worry about attacking.
If I'm playing Machamp, I can just Fighting Tag to break that lock.
If I'm playing Politoed(lol) then I can Leap Frog out of the lock.
Or just leave something with Cheap retreat active to do some damage, then retreat to something that has the OHKO.