You can obtain Pokemon that evolve into Steel Types early in the Game. Drilbur, evolving into Excadrill(Ground-Steel), which can be obtained in the WellSpring Cave whenever you see Dustclouds rolling in. If you want to catch a Steel Type that requires no Evolution, then you need to wait until you have unlocked Chargestone Cave, in which Ferroseed(Grass-Steel), and Klink(Steel) can be captured.
Other mentions include Karrablast, that can be obtained before Chargestone Cave and evolve into Escavalier(Bug-Steel) through a Specific Trade. Durant(Bug-Steel) can be obtained in Victory Road, if you are willing to wait that long.
Happy searching :)