Gas work always requires a permit, even if your jurisdiction allows a homeowner to do the work.
Depending on how far you have to move, you could go straight across through the studs, but it would be better to go up, across in the attic, and then down again. Boxes are not typically used for gas. A nipple comes straight out of the wall to a valve. Check the rough in spec for your specific stove as to where the the valve should be. This work will need to be done in threaded black pipe.