I'll skip Teemo, since you covered him already... The problem is less the damage he does (which is good but not spectacular) and more the fact that he's literally the only champion in the game with serious map control right now. An Oracle will not help prevent the map control issue short of actively and constantly sweeping for shrooms, and I suspect that the vision radius around shrooms is a big culprit here; is there any way you could look into adjusting shrooms to act like the game's other trap-type abilities, with no vision radius but causing their target to get revealed for a short time? I believe this would go a long way to addressing his issues without removing the good damage associated with the shrooms.
People who can build heavily defensive and still do serious disruption or damage, and people who can build heavily offensive and survive thanks to innate defensive scaling or mobility, seem to be the biggest problems in my view.
I've seen a lot of trouble out of Wukong, though thank god he's a bit rare. He can afford to build very heavily into offense and still survive between his passive and his ability to play mindgames with enemies. I suppose better players than I would have less trouble, but his damage still goes to extreme levels, particularly when you factor in the interplay between his Q and Black Cleaver. Very few other champions can double-dip that item as significantly as Wukong.
Jax and Olaf are two others who I've seen tend to be problematic, but less so thanks to a bigger lack of disengages. Jax can afford to build heavily into offense and expect to survive thanks to his innate defenses, and Olaf can afford to build full tank and expect to deal game-winning damage because of it.
I also see Cho'gath (enormous free health, allowing him to build extremely heavily into AP) and Darius (high-threat ult, good chasing power with FM, can build heavily tanky and shut out anyone but an opposing bruiser/tank) banned or dominate fairly often.
Ezreal shows up strong, too. He's able to build extremely heavily into offense and rely on mobility to keep alive, and his ult allows him to effectively farm an entire lane all at once thanks to higher gold income on this map keeping his ult damage above minion defensive scaling.
Frankly I suspect those are more problems with those champions than anything else, without much map-specific changes that could be made to correct the problem. The Ezreal issue could speak to a need to adjust minion scaling, I suppose.