In spite of the klepto nerfs, GP is the #1 top laner in the game statistically
http://www.op.gg/champion/gangplank/statistics/top
Yeah, I think we know what needs to happen. It's time for direct nerfs.
I'd prefer a semi Q revert where his Q costs 10 more mana and has only 15 mana refunded on kill. If GP wants to poke you out during his "weak early game" he will actually have to bring his ass back to the fucking base for mana more often.
Nasus on the other hand has descended to 49% win rate with klept and coin nerfs, but I think he's fine, his kit is already as oppressive as fucking hell with the "I outscaled you at level 6" thng he's got going on.