I was actually thinking of doing a similar run using only gift Pokemon, which are actually capable of making a decent team. In Violet City there's a man called Primo who, if you give him the right sayings, will give you a Slugma, Wooper, and Mareep egg. Then of course is the Togepi egg and finally Eevee from Bill. There are more, but those are the first 5 you can get.
Because your team has a bit of an electric weakness, I would suggest using Mareep instead of maybe Gyra, but that's up to you. As for your rival, setting it up so that he has Totodile (you choose Cyndaquil) gives him the most balanced team and makes him a bit more of a threat; if you want to go the opposite and have him have a team that's a bit more unbalanced, set it up so that he chooses Chikorita (you choose Totodile).
Yeah there are more gift pokemon than the ones I listed but those were just the first ones you can get. For the primo eggs you need to go to http://www.filb.de/games/tools/aikotoba?l=en and enter your trainer ID since the sayings are different for each game.