Even rusting that doesn't involve oxygen?
Hm, I must be wrong. Sodium is much more electronegative than iron, so it's extremely unlikely anything like that would happen (based on my directional intuitions only; I'm very bad at chemistry).
So what the heck is that soluble thing that you get when rusting iron in saltwater?
I remember getting something I believed to be water soluble (maybe I was very silly and was fooled by a very fine suspension?) by leaving a nail in a jar of brine on a radiator for a week. I guess I'll need to reproduce that and make sure (a) I remember everything correctly (b) it's actually a solution.
@robryk @mcc Iron chloride sounds reasonable - the brown stuff in these pics, excess precipitated out and filtered https://thegeoff.net/gr-wp/fractal-filters/
But what would happen with the sodium?
Ah, right, I confused the direction of electronegativity (I think; you chelate lots of other metals using sodium or potassium salts after all).
Ok, so this should be making the solution basic, so could be easy to disprove.
@robryk @mcc Ah, I get you, more "metal corrosion" than strictly "rust" as in iron oxide?
A classic in marine environments is galvanic corrosion, if two different metals are connected by an electrolyte (seawater being very good at that), then you get rapid erosion of the more reactive one, no oxygen involved.