I think the main reason why Teemo is so stupid to play against is actually in his E.

I realize that most people don't think of his E when they think about things that they hate about Teemo, but I think that it's a big part of why he's so hated.

First, he's a ranged champion and primarily played in a lane of melee champions. Most of the champions he beats up are either melee or ADCs. This means that the odds of it being melee players that hates him is rather high. If you give a champion that is a ranged some sort of auto attack modifier for additional damage, they will bully the shit out of melees. I believe this is also partially true for Kennen, but I digress. It isn't entirely a problem at first for other champions like Vayne since Vayne needs 3 hits, and while Vayne is also oppressive to a large number of melees, the fact that Teemo can deal a decent chunk of damage to you whenever he feels like it just by auto attacking once makes him stupidly difficult to deal with in many cases.

If Riot is going to rework Teemo, I suggest that they make his E into either something else entirely or a stronger/comparable active. Ranged auto attack modifiers with all of their reward behind one auto attack are almost always going to be problematic for melee champions.