How should I unstick an old gas appliance valve?
There is not much to fail on that valve, i think you are correct that it is the paint.  Put a little paint stripper on and let is soak for while. Clean it all up and run the edge of a flat blade screwdriver around where the valve handle meets the valve body.
Find the closest or the main gas shut off and have the appropriate wrench ready at that location in case you need to quickly shut of the gas supply.
check with your gas company before you do this, some times they will have to come out to reset the diaphragm after a meter has been shut off
Get the appropriate size pipe cap and use a pipe wrench to put it on the open end of the pipe with pipe dope so you can work on the valve.
Get a pipe wrench in order to secure the pipe assembly from moving while you work on the valve handle. Take an adjustable wrench ( crescent wrench ) and adjust it so it fits over the handle, The longer the better for leverage. Have a helper hold the pipe assembly from moving with the pipe wrench and then try to gently get the valve handle to move, use caution and just try to move it a little.  IF it starts to move then gently make short movements in both direction until you feel that is moving freely. If you feel you are not getting it to budge then stop.
With all of that being said, i would  suggest you ( or a pro ) just replace it with a modern 1/4 turn ball valve and not mess with the old one.
If you do then have all of your new fittings, dope and valve on site and ready to install. You will also need a test solution of soapy water to test the connections for leaks once the gas is turned on. You can find a small bottle of the solution in the plumbing section of your home improvement center. ( a pro will have everything need to do this.)
Check with the municipality and see if you are allowed to work on gas supply in your town.
Find the gas shut off up stream or if not then at the meter and shut it off.
Check with your gas company before you do this, some times they will have to come out to reset the diaphragm after a meter has been shut off
You will need Two pipe wrenches. Take it off at the threaded nipple coming out of the 90 elbow. The nipple may come out, replace it if it does. Put  new nipple on the  valve and then the appropriate fitting for the gas appliance you will be connecting, Use pipe dope on all the connections.
Did i mention, check with your gas company?
Disclaimer: I am not a plumber i just play one on the intertubes, proceed at your own risk.