There's nothing in the novel or film to preclude Clemenza or anyone else from having instructed Mike in firearms use prior to his Marines experience.

Also, you notice how Tessio is used kind of second hand. He has to get the package at the gate; he drives Mike and picks him up; he's sent to pick up the cake; his regime is assigned hospital duty. There are probably a few more instances. It's surprising considering that he was with Vito right from the beginning just like Clemenza.