Beating Koga

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

Step 1: 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.

Step 2: Ground works too

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

Step 3: 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.

Step 4: Navigate the invisible walls

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

Step 5: Fight

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