Poliwag can be found in both games in the following locations with any rod or Surfing: Route 6, 22, 28, 30, 31, 35, 43, 44, 45, Violet City, Ecruteak City, Blackthorn City, Ruins of Alph, Ilex Forest, Mt. Silver, Cliff's Edge Gate, Viridian City, Cerulean Cave, Safari Zone
Poliwhirl can be found in both games in the following locations with the Super Rod: Safari Zone, Cerulean Cave
Poliwhirl can be found in both games in the following locations by Surfing: Route 22, 28, 30, 31, Viridian City, Violet City, Ecruteak City, Safari Zone
The earliest Poliwag can be found is in Ecruteak City.
A King's Rock can be found in the deeper parts of Slowpoke Well. Multiple others can be found via Pickup. It is a 5% chance as a held item for Poliwhirl and Slowbro. It is sold at the Pokeathlon Dome Shop on Monday, Thursday, and Sunday.
From this point onwards, you can fight the gyms in any order, though you will need to retrieve the Machine Parts from the Cerulean City gym before you have access to the earlier portion of Kanto. Feel free to anticipate or postpone any battles as needed.
Gym #9 - Brock (Pewter City, Rock-type):
Rival (Mt. Moon, optional):
Gym #10 - Misty (Cerulean City, Water-type):
Gym #11 - Lt. Surge (Vermilion City, Electric-type):