Kled is one of those champs that was kind of perfectly balanced upon released, so unlike a lot of champs who people complain about being too weak on release and encourage riot to over buff until they complain about them being too strong (that turned into a mini-rant there), Kled never really received too man buffs or nerfs over time. And since he's always been a bruiser that's only really good at single target damage, he's just kind of had trouble finding a place in any meta.
It is a team game after all, and Kled doesn't believe in needing a team to start a team fight.
He's not at all bad. Far from it, he's worth playing (he's my favourite champ), but there's actually quite a few bad match-ups for him, especially when considering he's suppose to have a good early game. It especially doesn't help that armor and MR does very little right now, which means nuking him while Skaarl-less isn't hard if the enemy any kind of CC.