I actually had another Idea that would sort of reward Teemo for stalking into a lane and would serve to reinforce his scout identity while replacing an all out gapcloser.
Passive, Camouflage: If Teemo stands still for 2 seconds, he gains stealth for 4 seconds, as well as a 15% move speed buff. This refreshes infinitely as long as he stands still (but moving requires a full 2 stationary seconds to refresh the stealth again). On breaking stealth (by attacking or the buff wearing off), Teemo gains 35/50/75% AS for 3 seconds.
This isn't a true gapcloser, but it would help him gank a lane and adds to the secretive scouting aspect of his identity (he tries to get from one bit of cover to the next as quickly as possible) He could effectively stay stealth infinitely, but would have to gauge how much time he is wasting by standing still for the passive refresh and how much he should just use the MS and stealth to get in for a quick attack.
For W, maybe it could passively increase the MS buff his passive gives by 5/10/15/20/25% bonus (20/25/30/35/40% total). For an active how about something like: Killer's precision: for 6 seconds, your AAs and abilities cause you target to deal X% (maybe like 8/11/14/17/20%) less damage to you (only applies to the target last hit, and only reduces damage to Teemo) and you heal for a small amount on-hit while granting a small bit of movement speed (ideally with the heal scaling with AP).
I think giving him a true gap closer would kind of break him and remove a lot of cool options he could have, because then there would be no need for him to worry about how to get to melee range, or how to get out of a fight, and that would give us somebody like Nidalee or Fizz, and not a strategist like Teemo ought to be.