So, I know everybody hates Teemo, but I think the big problem with him is that he doesn't fit in anywhere. He's a scout, not something most teams want on their comp. He's not great in a teamfight (in my opinion) and not great at split pushing, he's just floating around somewhere. I could be totally wrong on that though.
But I don't think increasing his damage or armor would be helpful. I'd love to see it played off him being a scout, and make him a split pusher. No, we can't have Teemo tanking waves of minions, but altering his passive to buff nearby minions when stealthed would be a great way to do this. The buff doesn't need to be visual, something you could only see when you click on the minions. This would allow him to split push ahead secretly, although he wouldn't be completely hidden, and would still need to be near the minions to help - making him a bit easier to find (although the stealth would be a problem still).
I think something small like this would make Teemo usable in games, rather than just that person you don't want to see in any game.