Personally I find it's all about what happens in the early game that defines so called OP'd characters.
To cite what people seem to be jumping on, Nocturne is only good if he gets fed. Nocturne is pretty **** squishy. Other mages, any melee DPS, and most tanks can utterly demolish him in a one on one, and playing both with and against Nocturnes both good and bad, I've seen them both get absolutely DEMOLISHED in team fights. It's rare that a Nocturne corpse isn't floating around somewhere on Summoner's Rift. XD That combined with the timing you need to make the most out of his ultimate makes him anything but OP'd, in my opinion.
Another one who doesn't quite stand out so much in this thread yet I've still heard cries of "OP'd nerf pl0x" about is Master Yi, another squishy melee DPS who can be quite easily wiped out by any mage worth their spells if he doesn't play carefully. Yi is all about capitalizing on an opportunity to do a little or a lot of damage, then backing off, meditating, and jungling or killing minions in the meantime. Again if you don't feed a Yi, he is downright useless late game.
To cite a mage who people seem to scream OP'd about, Vladimir needs to get verrrry heavily fed to get his build set up to perfection. If he doesn't get that health or ability power boost by level 12, he turns into a secondary damage dealer at best, and a liability at worst.
And lastly, Evelynn, to talk about an assassin. Evelynn can be countered relatively easily by Oracles, and once again needs to heavily feed to become viable. Unfed Evelynns become dead weight as early as midgame, and if an Evelynn player makes one mistake, be it in ganking, team fights, BREATHING AS ANOTHER CHAMPION SNEAKS UP, she is dead as Karthus and Amumu literally are. ARE YOU READING? DEAD. She relies on stuns, status effects, stealth, and the element of surprise to get fed to the point that she can handle a 1v1. Counter that and you're gold.
And since it wouldn't be fair for me to not pick on my own main: Die a lot as Lux, and you aren't a support; you're a liability. Your laser deals abysmal damage and rarely gets unleashed because you haven't gotten the ability power or the cooldown to maximize its potential, your Light Binding pales in comparison to Ryze and Morgana. Your shield can't withstand a Cho Gath sneeze, and Lucent Singularity and Illumination are irritating at their best.
And there's my two cents. Keep in mind that I don't think any of these characters or any others need boosts. I'm just saying they don't need nerfs and need to be played right to be of use. Thanks for reading. <3