Since the AI in Pokémon Red/Blue was programmed to always use a "super effective" type attack, and Lorelei's lead-Pokémon Dewgong knows Rest (Psychic), which does no damage, this screams for setting up on Dewgong.
Since the type Psychic is super effective against Poison, I came up with this strategy:
Teach a Lv 2 Nidoran♂ the following moves:
- Toxic
- Double Team
- Substitute
- An attack - preferably one with high PP.
While Lorelei's Dewgong is out:
- Set up 6 Double Teams
- Set up Substitute,
- Hit Dewgong with Toxic
- Spend turns wasting PP from the 4th move until Dewgong is finished.
From there, keep poisoning the rest of her team with Toxic, keep Substitute up and heal with potions.
Is there another strategy that doesn't rely heavily on avoiding hits?