The problem with most of the champions you mentioned getting nerffed comes down to counter-play, or a lack there of.
Counter-play is the basic idea that everything shouldn't just be fun to use, but should also be fun to have used against you in some way.
The some way Riot has opted for is choice. They generally push for different mechanics to be countered with a range of different choices.
With Gragas - while he was fairly average in power by most respects, he just offered very little means of playing against him in lane.
Most lane match-ups allow a shorter-ragned champion (when taking into account abilities) to beat a longer-ranged champion if they trap the longer-ranged champion in their shorter range. This gives the short-ranged champion a way to win by biding their time, and the longer-ranged champion will always be able to win by out-ranging their opponent and wearing them down.
Gragas didn't allow that.
Gragas was extremely solid in a body slam + auto-attack point-blank assault, and his massive poke range and personal sustain made him essentially impossible to beat in a poke-war. While his lane strategy wasn't devoid of countermeasures, you had to contort yourself into really obscure, awkward strategies to mostly just break even.
Generally such strategies involved staying in a really difficult to maintain medium range where Gragas had to resort to poke, was punished for his melee auto-attacks, and wasn't quite close enough to Flash+body slam you in the face. But you're pretty much walking on a razor's edge, even with medium-ranged champions capable of blocking the body slam (Malazhar), to reliably gain traction.
And Gragas had no real trade-offs late for a very solid early game, where most early champions (LeBlanc, Shaco, Yorick) fall off a proverbial cliff late-game as a counterweight to their power. Being dominant early is something you can play against there by simply surviving, where late-game Gragas could still easily turn into the AoE damage/poke champion his team needed.
If you look at the other champions you mentioned - it's the same basic thing. Not to strong on paper, but very difficult to actually come up with meaningful counters to - be it counter-picks, counter strategies, counter tactics, or counter reflexive plays.