Well, Machoke is mediocre compared to both Machamo and Hariyama. I'd go with hariyama as it and Machoke have the same ability, guts, but Hariyama is much bulkier and can withstand more attacks. Good luck!
P.S.- this is for normal versions of the game. I am unsure what Nuzlocke really is.