When you only have one Pokémon, which is the one that is in your party, this NPC in Cianwood will give you a Tentacool. It is not necessary to remove Surf/Fly from your remaining party member. This can be done during any part of the story, including after defeating the Elite 4 and Champion. The NPC will continue to give out Tentacool infinitely, as long as you only have one Pokémon. Able to be of either gender or either ability.