Beating Koga

Every Pokemon Koga owns is Bug/Poison, so Psychic is 2x on all four. The difficulty is not damage, it is attrition.

Bring a Psychic

Kadabra or Alakazam is the obvious answer. The Mr. Mime you trade a Clefairy for on Route 2 works just as well.

Ground works too

Dig and Earthquake are also super effective on Poison-types.

Stock status cures

His Venonats spam Sleep Powder, Stun Spore, PoisonPowder and Toxic. Bring Awakenings, Antidotes and a few Full Heals - remember that in Gen 1 waking up costs you the turn as well.

Navigate the invisible walls

The gym floor is a maze of invisible barriers. Follow a wall rather than wandering.

Fight

Reward: Soul Badge (+12.5% Defense, Surf usable) and TM06 Toxic.