I just did this. Use a good wrench, one as long as you have - let's you apply more pressure and, more importantly, better control how much pressure is being applied. I would use vice grips only as a last resort as they tend to grind off the flats on the valve, thus reducing your ability to get a good purchase on it. If you don't have a wrench that will fit, I'd suggest buying one - that and patience may make the difference between success and real trouble.
It also helps to tap on the valve body using a small hammer and a drift pin - tends to break loose any corrosion that may have built up in the threads.
I had to apply a lot of pressure to move the valve in my tank - more than I'd like but it turned out okay! Once you get it moving a bit, alternately loosen/tighten until the threads seem to be freeing up.
I had a shallow plastic container handy to catch the inevitable outflow of gas left in the tank. Disconnect the battery and make sure that there's no way to drop a wrench across the terminals or neg terminal to ground, generating a spark!