Counters: non-auto heavy champs with comparable damage to him(assassins and some fighters), tanks, adaptive helm, sweeping lens, oracle's alteration, control ward, warden's mail. You basically need to cc him(slow, root, stun, knockup) and then wail on him with non-auto attacks. If you end up fighting him as an auto-heavy champion, try to bait out his blind by hitting a few autos on him then back off. If you're a fighter or a tank, buy adaptive helm. Mercury Treads are also helpful(reduces his blind duration). As for shrooms in lane, follow your minions at a bit of a distance whenever they move so they detonate it, if its off to the side push your minions into it then back off(you can change the minions movements by getting in their way).
Note: Teemo's greatest strengths are Attack Speed and Movement Speed.