Been training Koffing ever since. I Surfed up near the Olivine beach, and fought wild Tentacools to get Koffing level up to ~L18. After that, I went and fought all the trainers I've been skipping at the National Park. Then I decided to backtrack and explore all the Surf routes previously unreachable, and cleared half of the Dark Cave. I've been training Koffing ever since, using him in most Trainer battles.
Oh, the rest of the Koffing eggs hatched. I released them all though. :P
After that I went to Violet Town and went inside the Ruins of Alph. With Surf available, I can now clear 80% of the sidequest I believe. I'll be finishing that up before progressing on.