Are you able to buy great balls yet? If not no worries, I'm pretty sure that if you go back to route 1 and throw pokeballs at the lv2-3 Pidgey and Rattata you will catch one quickly enough, no damage required. Then you can start your journey with your new friends from there...
EDIT: Actually are you able to get back yet? If I remember right, you can't head backwards through Mt Moon due to a ledge so you have to take Digletts Cave. I guess your not there yet.