Yes, it is possible as you'll have to get lucky after soft resetting and uncertain amount of times. It is possible it just takes time!
To do this just save before battling him, battle him, then get your Starter, if not shiny then press L+R+Start or Select. This will reset you to your previous save point.
Hopefully I've Helped!