I don't often do club-style photography, but recently I covered an afterparty at a pretty cool lounge here in Boston - I also use a 5D3, and my first move was setting ISO to 3200, which stayed relatively static all evening (some bumps and pulls here and there). I had my 580EXII mounted on-camera with a Lumiquest ProMax diffuser (my first time using it).
Lenses were either 50mm f/1.4 or 70-200 f/2.8L IS II for these shots. I prefer to shoot the 50 near 1.6 or 2.0, and usually opt for more candid and artistic shots than trying to pose everyone and get them all in focus,
Here are two shots with the 50 @ f/1.8, shutter speed 1/160-200, ISO 3200 with FEC at probably -1 (although i had the diffuser on which further lowers the perceived output)
The bottom shot is with the 70-200, at f/2.8 and shutter speed 1/50, ISO 3200
If you're shooting at f/4 you probably want to lower your shutter speed further. I'd say 1/25 or 1/30. Also try setting the flash to fire at second-curtain. Run through a range of FEC settings until you find something that gives a good balance of foreground and ambient light - often i find when reviewing images that the whole image, although it looks balanced, seems sort of dim and generally underexposed - for that you might try bumping up the ISO a notch if you notice it during the event. If it's too late, Lightroom works wonders