So, er....how did Khan gain control over South Asia and the Middle East, including Iraq? I can't see him using very brutal tactics at that point in his career, as it was stated that he was one of the least violent dictators, until he was attacked from outside his empire.
Just because he didn't massacre people under his rule, doesn't mean he wouldn't use brutal tactics in the process of achieving that rule or he wasn't violent. The final act of "Space Seed" shows he wasn't adverse to violence and threats. Earlier we see he has quite a temper.
He probably gained control using traditional means, using his charisma to convince people to follow him and then use those followers to usurp the current rulers.