Most cost-efficient runes at lvl 1 for Teemo (in order of gold value):
REDS: AS, AD
YELLOWS: Armor, AS
BLUES: AP, MR
QUINTS: AP, Lifesteal, AS, AD
Efficiency is calculated by the gold value of each stat * rune stats. Gold value from each stat is derived from common items. For more information, refer to this: http://leagueoflegends.wikia.com/wiki/Gold_Efficiency
A slightly outdated quantitative analysis of Season 2 rune stats can be seen here:
NOTA BENE: ATTACK SPEED
You'll notice that generally AS-related runes have very good gold efficiency -- this is because in Season 3, AS was nerfed across the board. However, it impacted only really daggers; most high-end AS items tend to have good cost-efficiency like in Season 2.
The changes to attack speed for Season 3 runes can be seen here:
"This makes attack speed runes worth more now. A full set of marks is 15% attack speed, which is 1.25 daggers. A full set of damage marks is 8.55 damage, which is part of a Long Sword. Damage marks are 342 gold's worth of stats; attack speed marks are 500 gold's worth of stats."
Because Teemo is one of two hybrid auto-attackers in the game (the other being Kayle), attack speed's impact is 2x efficient, as it multiplies both AD and AP damage.
NOTA BENE: COOLDOWN REDUCTION
Teemo does not scale efficiently at all with CDR early game.
"Nonsense! I want to put a million shrooms on the map with my Nashor's Tooth," you say, but hear me out.
This poor scaling is due to something called "AP Scaling per second".
The excel sheet: https://docs.google.com/spreadsheet/ccc?key=0Aide09023sspdFFrS3JxcFZ5bFFuRm90OHZXMHJNU3c#gid=56
It is important to understand this to see why Teemo is fundamentally weak at scaling with CDR. His W, which allows you to spam Move Quick, does not do damage. His E, an autoattack buff, does not scale with CDR either. This leaves Teemo's Q and R as the only things that are CDR reliant for DPS. Taken by its glance, Teemo has one of the worst CDR scaling in the game -- 19.11% effect on AP-scaling DPS compared with the standard 66.67% for Mid-AP champions.
That's not all -- the 19.11% effect is assuming that shrooms are being used like a nuke -- meaning that you are maximizing them at all times by keeping shroom stock at 0, and that you are blowing them up on an enemy champion at all times at every battle.
Of course, thats not how Teemo functions. The complicated part is that Teemo is rewarded for inefficient use of his ult because shrooms can also be used to provide vision/ward, to slow enemies when escaping, to catch them when they are engaging, not simply blowing them up in battle. Hence while Teemo has a 19.11% scaling for AP/CDR, it is not fully reflective of the 'stockpiling' of future damage taken from current mana costs. This is not something that other champions can do, despite having better CDR scaling -- Ahri cannot simply 'reserve' her ult at various places on the map to do future damage. She has to use it then and there, in a battle.
Even given the unique scaling nature of Teemo's ult, CDR is ultimately inefficient compared to simply building AP for it. The tradeoff of stronger shroom damage vs. more shrooms is complicated, but I have sided with more shroom damage, because of the incredible scaling that the Q and E provides as a spin-off benefit from AP in terms of the tradeoff between AP vs CDR on Teemo.
After a critical amount of AP, CDR becomes viable -- but it should never be rushed on Teemo. Nashors, Athenes, and Morello are viable AP items on Teemo late-game, and one of many situational picks.
But early game (before level 6), CDR does absolutely nothing. This is why CDR blues are not considered for Teemo.
Teemo also has no mana issues early game, so it is also why MP5 yellows are not considered.
RUNES FOR SITUATIONAL MATCHUPS
Remember to switch out armors for AS, and MR for AP, depending on the lane. If you are playing Mid lane Teemo you do not need armor most of the time; if you are playing Top lane you do not need MR most of the time.