Slowbro and Gyra usually. Although you have to be careful with gyra. Usually I switch in gyra to take the dpunch or payback while providing the attack debuff, switch again to something that would resist stone edge and machamp is usually pretty manageable after that. Like I said, the biggest loss is that they know 3 of my pokemon.
edit: I think most people in general don't think beyond what other lead can deal with machamp effectively. It sucks, but its a lead you have to play around, but its possible to minimize the damage you do take.