Well I am trying to get this build:
[SET]
name: Physical sweeper
move 1: Earthquake
move 2: Megahorn
move 3: Stone Edge
move 4: Fire Punch / Sucker Punch
item: Leftovers / Choice Band / Life Orb / Choice Scarf
nature: Adamant
evs: 6 HP / 252ATK / 252 SPD
[SET COMMENTS]
<p>Nidoking is easily one of the most diverse attackers around, and woe be to most Pokemon that attempt to wall this. Earthquake is your main attack; Megahorn hits annoying grass types; Stone Edge is for fliers and bugs; and Fire Punch deals with Skarmory and Bronzong. If you have some other response to Skarmory, consider Sucker Punch, which is an excellent response to obnoxious Psychics and Ghosts who outspeed you. You can use Choice Band here for more power, Choice Scarf for speed, or stick with good old Leftovers. Life Orb is for the sweep-minded and could be effective given Nidoking's resistance to Stealth Rock and Sandstream.</p>
So I guess evolve it at 16 once it turns to nidorino is the best option.