It cannot be understated how amazing Starly is. Its stats are competent, it evolves early, Staravia gets Intimidate for an ability, and Staraptor even learns Close Combat to turn Rock and Steel types from walls to prey. Use it. By now you can easily catch one in Route 204 at a good level and destroy Gardenia.
Also, catch a Bidoof as soon as you can. It makes a great HM slave. Replace it when you can catch Bibarels in the wild.