Gavin,

Did you remove the rock guard?  The 1/4" steel plate that protects the
regulator and valves is held on by 2 bolts which are a breeze to remove.
With that gone, I can't think of why you'd have any trouble getting the
regulator off.  I just did mine about a month ago.  On mine, there was a
'Y' for splitting the pressure-regulated gas to the stove and fridge lines
which just spins off of that side of the regulator.  On the other side of
the regulator there are male threads which screw out of the on/off valve
counter-clockwise.  Mine did not have a 'large nut that holds it in place'
  like you describe.

As far as the rust on the tank, mine has that too, but I doubt that it is
an issue, since the tank wall is so thick (notice the unprofessional,
inexperienced tone of that statement).  Maybe it was the $300 replacement
tank talking to me.  I thought about painting mine when I had it off, but
time constraints didn't allow it.  You could use some Corroless and marine
grade paint in your area, I guess.

HTH,

John