The pokemon you recieve (Starters, Eevee, Beldum, etc.) are actually the easiest to get shiny. Simply because you can save in front of it and just keep restarting until you get one.
So, the answer is yes, you can get a shiny Beldum from Steven. The only thing is that it may take some time and a lot of patience.