[Before I begin, I'm going to say that I might be rather biased because I'm basing my opinion on my experience with his Majesty.]
For a team style, I would be thinking that some form of semi bulky offense would be a good idea to combine with our Nidoking set. If everything was a faster sweeper, the slower Nidoking might seem rather out of place. I'm thinking a non-weather-using, but fully-weather-abusing kind of team would be good in this case.
Gyarados @ Leftovers
Trait: Moxie
EV's: 80 HP / 184 Atk / 20 Def / 20 SpD / 204 Spe
Adamant nature (+Atk, -SpA)
-Dragon Dance
-Substitute
-Waterfall
-Bounce
Gyarados' great type synergy with Nidoking has
already been mentioned before, so I don't think I have to go too in-depth on that. Both still have Starmie problems, but still. Gyarados offers a great physical attacker to the team to compliment Nidoking's Special assault. Gyarados - especially with that Substitute - can come in on special walls like Bliss/Chansey and set up. They probably won't status Nidoking, as he's immune to T-Wave and Toxic, so Gyarados gets an almost free switch in. After Nidoking sufficiently weakens the team, Gyarados can also come in and pick up the pieces. Gyarados also can hugely benefit from Rain, which is something Nidoking has trouble with. Paralysis support from Bounce also helps.
Sableye @ Leftovers
Trait: Prankster
EV's: 248 HP / 124 Def / 136 SpD
Calm nature (+SpD, -Atk)
IV's: 0 Atk
-Will-O-Wisp
-Taunt
-Recover
-Foul Play
Yes. I am biased. I love Sableye. Sue me.
Sableye both gives and receives from this pairing. One thing that's obvious Sableye gets is the fact that Nidoking stops completely something Sableye hates - Toxic Spikes. Nidoking also lures in said Blissey and Chansey, both of whom Sableye completely walls and can outstall to death so long as they are kept Taunted, unable to status or recover. Again, from Nidoking, Sableye can get an almost free, status-free switch in (though paralysis isn't really minded much). Sableye also helps the overall core by throwing around those burns everywhere, and stopping dangerous Baton Pass teams, Dual Screeners not named Espeon and Xatu, many members of common stall teams, many more member of common physically inclined HO teams, and Alakazam/Reuniclus (Foul Play, while using their lower Attack stats, still 2-3HKO's both, even of they have minimizing natures and 0 Atk IV's).
With Gyarados' EV's, his Subs are guaranteed to not break from a burned Ferrothorn's (uninvested) Power Whip. On the EV topic, Gyarados' Sub also lives through a Timid Choice Scarf Politoed's Scald in the rain with those 20 SpD EV's. The 204 Speed is to outrun Alakazam after 1 Dance. Sableye's 248 HP makes it so it takes reduced damage from Spikes and such, and the 136 SpD hits a jump point.
So that's my contribution. Paralysis support would be nice for things that don't need to be burnt, as well as the necessary Stealth Rock and other weather stops.