Yeah, I just take Malady because it's cheap. I often sell it back later, if I make enough money, and replace it with Rabadon's Deathcap, Liandry's Torment, or Runaan's Hurricane.

You don't have enough AP to make Malady more worthwhile than Wit's End and Mercury's Treads are more important on Teemo for survivability. However, Malady is an extremely cost-efficient item, so I suppose it works. But the defense of Wit's End appeals to me more.

It would also make up for the lack of magic resist in your items. Iceborn Gauntlet is also a possibility for even more kiting. It'll also make up for the armor deficiency as well as generate quicker mushrooms.

I would build Malady, Nashor's Tooth, Blade of the Ruined King, Frozen Mallet, Berserker's Greaves, and Warmog's Armor or Randuin's Omen.

Always Frozen Mallet, even more so on an On-Hit Teemo. It was just that times used to be that On-Hit would get perfect stats.

Armor from Madred's Bloodrazor, magic resist from Wit's End, hp from Frozen Mallet, AP from the old Malady or Nashor's Tooth, all the while gaining AS and on-hit effects. This was then rounded off with a Guardian Angel for a surprisingly durable and high-damage Teemo with an AS of approximately 2.5 AS. It was extremely niche.

Nowadays, it's hard to find an armor-based component that fits in well with On-Hit Teemo, especially if he goes toplane against mostly AD bruisers.

Well, you can go Rylai's Crystal Scepter or Frozen Mallet for extra HP. Or Guardian Angel.

Yeah, but no armor, so Teemo still squishy, q.q

That's what I said when it came out XD I was like..."So it's Madred's Bloodrazers, but better?" and then I made myself an on-hit build folder via LoL Tools.

Although, with the AS that have been added to Blade of the Ruined King, on-hit Teemo might be back in action!

Nope, still sucks. The reason going attack speed is useless and you failed is because you need to build damage and penetration with it, which you blatantly failed. Teemo relies on AP because his Toxic Shot scales well with it, and so does his Noxious Trap. AD does nothing for him; you might as well just play an AD Carry for those purposes.