Hello MOBAfire. This is Okibruez (American server).
This is my first build that I've posted so be constructive please, and I hope you enjoy the build and advice. If you do try the build and win big with it, go ahead and let me know. I'll always be happy to hear success stories.
Teemo is often played as an AP Mage Nuke, relying heavily on shrooms and blinding dart for most of his damage. This is not that build, as I'm sure you've noticed. He's also often played as an AD carry, relying on his abilities only as bonus effects. This is not that, either.
This is a hybrid build focusing on bringing every aspect of Teemo into the battle.
These are: High mobility, moderate map control/detection, strong harass, good scouting/ambush capabilities and incredible damage sustain.
This build uses these aspects to pick out a single target and burst them down to low health, then let the sustained harass drop them the rest without trouble.

EDITS:
- Added a link to the masteries page, alternative runes, and cleaned item list.
- Minor edits, further cleaned lists, correctly linked masteries, fixed skill sequence.
- Changed final buys from Nashor's Tooth and Guardian Angel to Wit's End and Thornmail

Main runes:

9x Greater Mark of Precision
9x Greater Seal of Vitality
6x Greater Glyph of Scaling Mana Regeneration
3x Greater Glyph of Scaling Cooldown Reduction
3x Greater Quintessence of Scaling Cooldown Reduction

To explain
These runes all give Teemo much needed boosts, especially with the items used.
The Marks of Destruction all grant some penetration to both defensive stats, and you'll need every scrap you can get. Of course, the hybrid build and your natural abilities will allow you to overcome most enemy's defenses simply by targeting both, but it's not enough against anything with a more defensive build.
The Seals of Vitality grant you some much needed durability over the course of the game, and often that slight difference will be enough.
The Glyphs of Clarity and Celerity will allow you to use your abilities more often... And with more Noxious Trap on the field and more uses of Move Quick to get you where you need to be without going back to base, you can stay out longer and do more for your team than many would expect.
The Quintessences of Celerity grant you even more uses of your abilities, and that's always a good thing.

Alternatives:

If you think that the build is a bit CDR heavy then you could switch out the runes of Celerity, maxing out all 9 glyphs as Clarity. For alternative quints I'd suggest using:

Greater Quintessence of Vitality for the solid HP boost. Teemo suffers from being one of the squishiest targets while still being the number one target on your team, (Yes, even above your AP Nuke or AD Carry.) so alittle more crunch never hurt.

Greater Quintessence of Precision for even more damage penetration. Because tanks are always hard to melt, but every bit makes a difference, and on the squishier targets True Damage is amazing.

Greater Quintessence of Movement Speed
Get in fast, get out fast, and don't let the taunt hit you on the way out. Teemo is already one of the fastest characters on the map with this build. Go alittle faster and drag out a chase as long as you need to.

30 points in offense is nothing short of insane, you say?
You need more defense or support you say?
This isn't a support build, nor is it meant for heavy combat where every extra second spent standing is needed, so those don't matter nearly so much.

For your summoner spells you definitely want to look at those that increase your mobility, damage, or durability.

Must Haves:

Teleport Probably my personal favorite summoner spell for Teemo the long and short of it is really quite simple: It meshes with your abilities perfectly to let you show up where the enemy team doesn't expect, or want, you to show up, as well as giving you a convenient escape when they think they've got you trapped.

Ignite What a great spell this is for Teemo. With all your damage over time effects running was never a guarantee at life, but throw this in the mix and it's nearly a clincher at securing escaping enemies. As well, the added dps can make or break a successful ambush, and the reduced healing the target receives? The icing on the cake.

Ghost Not bad for Teemo. The extra movement speed is nice and it's great for escapes, but not much use in helping you chase down someone else... You'll either not catch up regardless or have no trouble running them down and finishing with DoTs.

Personal Preferences:

Surge A short duration boost in damage, this spell is a solid choice for you. Especially since it boosts both attack speed and AP, giving you an even bigger boost to damage than most champions. Stronger than Ignite in terms of overall damage boost, but alittle weaker in terms of finishing a wounded foe.

Heal A sudden burst of health can make the difference in a fight. We all know it. It might also let you sit around in lane longer in the beginning of the game.
Buuuut... it doesn't scale well enough into end-game to make it the best of choices and honestly, the extra health isn't enough to make it worth taking just to survive that extra hit from an angry Tryndamere. Maybe if you were playing a support Teemo instead..

Flash Not bad to help you get out of certain doom, but not as useful as it was, and overall, there are better choices for you. If you're really use to this then there's no real reason not to, but it's not the best.

Absolutely not.

Clairvoyance Might seem tempting but you already have Noxious Trap to give you vision on the map. Let someone else on your team (Like the tank or support) take it instead.
Clarity You might think that this would come in handy but the only abilitiy that you'll be using religiously is your ultimate, and by the time it comes up the runes should be giving you enough mana to keep you in lane for some time yet.
Cleanse You're way to squishy to make this a worthwhile choice. The number of times this will mean life or death are very very low for you indeed.
Exhaust If you were running AD Teemo, maybe. If you're using this build you already have 3 sources of slow, and Blinding Dart shuts down auto-attacks just fine.
Promote Doesn't actually add to your effectiveness in a duel in any way, and you shouldn't need to backdoor at all.
Revive There is no reason to take this at all. By the time it will make a difference, the enemy team should be able to run roughshod over you if you try to take them on solo.
Smite You're not a jungler. That is all.

By Level:

Descriptions:

Camouflage is your passive. Whenever Teemo stands still for 2 seconds, he becomes stealthed and cannot be seen or targeted except by units with stealth detection, or if revealed. When you commit any action the stealth breaks, granting you the Element of Surprise buff which increases your attack speed by 40% for 2 seconds. You can still be struck with AoE or skillshot abilities while stealthed; and knock-up, knock-back, or pulling abilities will force you out of stealth.

Toxic Shot will be, for the most part, your bread and butter magic damage. As a constant passive bonus to your auto-attacks you're going to want this at level 1, and maxed at level 9.

Move Quick grants a passive movement speed boost that scales with level and, upon activation, doubles the bonus. Check out what you'll be facing and decide if you take this at level 2 or level 4, but you'll max this second regardless. (More skill-shots and magic damage will be easier to avoid with this taken at level 2.)

Blinding Dart deals magic damage and causes the target have a 100% miss chance with auto-attacks for a short duration. It's saved my life more than once, and it's great at shutting down AD heavy champions who rely on their auto-attacks for most of their damage output. Take this at level 2 if you're facing an AD carry, or level 4 if it's the AP nuke, but you'll max this last regardless.

Noxious Trap is your ultimate, and a deadly one it is at that. Noxious Trap drops an explosive, poisonous mushroom on the ground near Teemo. The mushroom automatically stealths after "charging" for 2 seconds and detonates when any enemy unit, from minions to champions, moves through it's area of effect. It afflicts all nearby targets with a damaging poison and reduces their movement speed by a moderate amount. The traps last for a full 10 minutes after being activated, and also reveal a small area of the map around them as if they were Sight Wards, though the area revealed is much smaller and lasts a short duration after the mushroom is destroyed. You'll put points in this every level it's available.

Starting pick:

Ruby Crystal Right out of the starting gate, this is my go to item. The flat health bonus is better than any other base item you can buy, and unlike with Doran's Blade, the Ruby Crystal can (and will) be built into other items.

Boots

Your choice of boots will depend heavily on the enemy team, but you'll end up using one of three.

Boots of Swiftness would be my first pick, and personal favorite. They'll give you a better boost to movement than any other pair, and there there will often be enemies that buy these as part of their build, or more rarely, just to chase you down. Pick the same boots and keep just out of reach.

Berserker's Greaves would be my second pick. Movement and attack speed bonuses wrapped up nice and neat? Yes please.

Mercury's Treads is my final choice in fits of desperation. If the enemy team is running CC heavy, or very AP geared, these are always a solid choice to let you survive to run and fight again for just that much longer.

But why not Mobility Boots, you ask? Because you'll go fast enough without, and activating most of your abilities removes the bonus speed. As well, if an enemy hits a Noxious Trap on the other side of the map, it still counts as combat and removes the speed boost. Overall, too many things that remove the bonus for you to get much benefit.

Early Game

Phage Grants you alittle more health and damage, and comes with a useful on hit effect.
Vampiric Scepter Lifesteal. Works well with Phage, and builds into a later item.
Hextech Revolver Solid AP bonus and spellvamp.

Early mid-game

Hextech Gunblade Grants good AD and AP, with lifesteal and spellvamp. Also comes with a useful activated ability.
Zeal Bonus Movement Speed, attack speed, and slight crit chance. Builds into Trinity Force
Sheen Bonus AP and Mana and a useful passive.

Mid-game

Trinity Force A moderate bonus to almost every stat you want boosted and has the passive benefits of the component parts (On hit chance of slow, and upon activating an ability, increase your attack damage to 150% of it's normal value for the next attack).
Madred's Bloodrazor, a great item for you that grants a bonus to attack speed and damage, and grants an on-hit unique effect that deals a portion of the target's maximum health to it as magical damage.

End-Game

Wit's End Good Attack Speed, some MR, and two nice on hit effects.

Free Slot

The last slot depends entirely on both teams, and you should think throughout the entire match on what to buy.
If the enemy is focusing you whenever you show up (and if you're this far into the build, they should be,) a solid defensive item is a good choice.
Smart picks include Guardian Angel, Banshee's Veil, or even Force of Nature or Thornmail, depending on their primary source of damage.

If they're not dropping you whenever they see you than think on items to further boost your own damage. Malady, Black Cleaver, Nashor's Tooth, Ionic Spark, or Phantom Dancer all mesh well with your abilities and boost your damage and battlefield presence by a large amount.

You've seen the build and I hope you understand it. But here's where it all comes together: How to run Teemo with this build.
First; be aware that you can have 4 phases of gameplay, depending on how you do, rather than the usual 3, but don't be ashamed if you can sit in lane and farm the entire game.
The phases you will go through are

Early Laning. During this phase, focus on harassing the enemy team and last hitting minions. Only move to secure kills if your laning partner initiates it. Yes, laning partner. This build doesn't have enough early game damage to be anything but passive if you get put into mid lane so try to avoid it.
Harass. Everyone else is still laning, but you can stop focusing on minions as much to focus on poking the enemy teammates as much as possible. Don't be afraid to leave lane to drop shrooms at key points (near baron/dragon, at forks in the jungle path, near the blue/red buff) as this will make the next phase easier on your team.
Ambushes/Gank. During this phase everyone else will focus on ganking but you'll do the opposite. Don't be afraid to leave your teammates and push the side lanes. It'll draw someone from the enemy team to you, and you should be able to win most 1v1 duels if you play smart. Failing that, find your target and get the drop on them before their team can intervene, then make a dramatic escape with Move Quick and your passive, Camoflage.
Teamfights/Pushing. With this it comes full circle. Hang back and content yourself with minions until someone else engages the fight. Harass the enemy team during the fight, and secure both team's escape routes with shrooms and quick movement. If both teams are deadlocked, it's easy to slip away and push a lane more aggressively, relying on your abilities to keep you forewarned if an enemy does approach, and to let you easily escape (usually to bait them to where your team is).

When you ambush someone, you want to make sure you have every advantage you can, but try to keep at least one of the following.
Control of the terrain: a nearby turret, fields of shrooms, allied minions or even a teammate. Anything that will make the enemy avoid an area, or failing that, hinder their movement can be used to help you turn a 1v1 brawl into a 1v1 chase where you have every advantage.
The Element of Surprise: When they least expect it, attack from where they were sure no attack could come. Use shrooms and Camoflage to great effect and attack from the middle of the lane when they could have sworn noone was there, jump them from the bush they just ran through, or wait for them to finish your tower and strike from the ruins (or finish theirs, and lurk there while they mop up your minions)
The "High" ground: They just solo'd the tower, threw down with the dragon, or barely escaped your team with their lives. You took care to get red buff, place a shroom where they'll walk, can get your Element of Surprise buff in a flash, and have a full HP bar too.
Have one of these, the odds are in your favor. two and the odds of loss are beyond low. All three and you've already won.

Finally: How to burst.
This is a burst combo that puts out tons more damage than any player expects Teemo to be able to dish out so fast, and it can melt squishier opponents in a flash.
The set-up: Make sure you have Trinity Force and Hextech Gunblade finished, with the activated ability on the gunblade up. Make sure Ignite is up, and drop a Noxious Trap where you're sure the target will walk, then let Camouflage activate right where the shroom is.
The combo: when the target detonates the Noxious Trap, hit them with the Hextech Gunblade, and follow with Ignite. Immediately after, hit Blinding Dart right before the auto-attack to get the trinity buff. Follow it with move quick for a second trinity-buffed auto-attack, and drop another shroom for a third. If they're still alive to fight, the shroom will activate shortly and secure the fight, but this has enough burst without the second shroom to deal over 1.5k to a single target in slightly less than 4 seconds. This is, of course, against squishy targets.
To simplify
1: Noxious Trap detonates
2: Hextech Gunblade (Breaking stealth and granting the Element of Surprise buff)
3: Ignite
4: Blinding Dart
5: auto-attack
6: Move Quick
7: auto-attack
Using this combo I've melted many targets before they could do anything at all, including killing Zilean before he had time to activate his ultimate, Chronoshift.

Benefits:
Strong sustain
Strong burst
Cheap component items
Strong mid -mid late game.
Strong against single targets
Uses both AD and AP, difficult to defend against
Fast movement

Cons:
Weak defense
Long Cooldowns
Overall expensive items
Weak early game
Weak against multiple targets.
Uses both AD and AP, lower damage from each
Global taunt

Honestly, I've been called a noob and worse for not using the AD or AP builds others favor, but I have my reasons for not wanting to run them.

The flaws in AP Teemo are:
Reliant on location specific effects
Non-existant sustain
Crippling over-specialization

The flaws for AD Teemo are:
Weak overall damage (No Magic for your Q or R)
No ability synergy (No bonuses for using abilities)
Crippling over-specialization
Teemo isn't an AD Carry: No attack damage boosting ability

Teemo has a broad range of abilities that make him well suited to supporting his team by crippling his foes, but most of his abilities don't grant him the sort of raw power that one or the other of those builds require.
However, this build requires the player to be willing to run from a fight, to have extreme map awareness, and a lot of cash to finish. Do it right, though, and by end game the entire enemy team will have purple eyes over their heads, and won't move off the summoning platform without another teammate to hold hands with.
As my very final thought; thanks to JhoiJhoi. Her guide on "How to build guides" can be found here, and without it this was a mediocre page at best.