My solution: EV Train, EV Train and EV Train even more. I'm goin for Hitmonlee because I need him for my Pokedex, so I'm trainin my Tyrogue in the B1 of Mt. Moon, where it's 100% wild Paras, so I get 1 atk ev point every time i kill one.
It's a little bit challenging because I think my Tyrogue's nature favors defense over attack, and I already have a Hitmonchan... :\ I picked the wrong Hitmon at the Dojo because Hitmonchan's stats suck, and his Elemental Punches are a joke with his poor S.Atk. (Note: This is on FireRed, where the elem. punches aren't physical attks)