Firstly I want to say that GP is not so broken as he looks like. It takes a lot of time learning his playstyle and as a GP main i still sometimes need to practice in custom games the combos and the timing when to shoot barrels. Well, ofcourse GP has problems but not only for his opponents but also for the player who's playing him.
In my opinion the only thing Riot should ever have touched is the barrels. Well, they have tried to nerf them but with the wrong methods. Back ago, in patch 5.17 they added the 0.25 second cast time on barrels which made it impossible to do some of the wombo combos with them as you can't place barrels so quickly anymore. This makes things clunky for skilled GP players and isn't the right way how to balance Gangplank. Powder Keg bonus dmg reduction in patch 5.18 is what Riot should have kept doing. They could even have removed the whole bonus dmg as an AoE crit is enough to keep him relevant. I don't even understand why they had to put that bonus there when they made his rework. Then in 5.21 came the Parrrley and base HP nerfs... Doesn't Riot understand that his barrels are the problem because people can't play against it (either it's undodgeable or people are too lazy to try disarm it...). Another thing why patch 5.21 nerfs were bad is that it doesn't affect good GP players. Myself I eliminate the mana problems by starting with Mana Sapphire and the HP reduction by never fighting my opponent (ofcourse, I sometimes use barrels for poking). Riot made GP's laning pure afk farming.
So what is the way to nerf GP? Simply make it easier to dodge the barrels by increasing the time between linked barrel explosions. This was already mentioned in an another thread when patch 5.17 came out.
Summary:
Buffs:
Remove cast time on Powder Keg (so GP players can use their skills once again)
Revert Parrrley & base HP nerf
Nerfs:
Remove bonus dmg to champions on Powder Keg
Increase time between linked barrel explosions (to make them easier to dodge)
Possible Powder Keg armor penetration adjustements could be made if they are needed.