conspiratemus

OK....
1) > "Does this look like normal clearance between chain and frame to you?"
No, there is excessive clearance between the chain and your dropout. You took this photo after inserting an extra spacer on the drive end of the axle, right? 2 mm clearance from the outer *edge* of the chain should be adequate, which is what you get with 4 mm of space between the cog face and the dropout. Any more than that and you end up with excessive asymmetry and a weaker wheel, as you alluded to when you redished the wheel by a half-turn on each spoke. That's a lot.
Is that a 9-speed chain like it should be?

2) Yes, it's rusty. I'm sure it wasn't rust or scale or other foreign-object debris that was rubbing on the 13T cog that started all this...

3) Your locknut on the drive side is sticking too far out beyond the cassette lockring. The locknut wants to be no more than 4 mm outboard of the outer cog face, so when you put a lockring on, the locknut will be just barely peeking out above it. The reason it's sticking so far out is because you moved the spacer from the non-drive side to the drive side, correct?

4) Indeed you did and indeed it did. To keep our terms straight, it is not two locknuts over there on the non-drive side but instead it's one locknut (FH-RE011) jammed down onto one bearing cone (FH-RE107.) Universal practice is to provide a washer between a locknut and whatever that locknut is supposed to lock, in this case the adjustment of the bearing cone against the balls in the hub. The washer on Campy hubs will have a little dog on the inside diameter that engages the slot cut lengthwise in the axle, which prevents the washer from turning (and then turning the cone, disturbing the adjustment) when you tighten the locknut down against it. (Although in practice, that's what cone wrenches are for.) Any additional spacers required to make the OLD come out right (130 mm in this case) go in here as well. The 8-speed Record hub I have in front of me, same vintage and design as your 9-speed, has an aluminum spacer as well as a black steel dogged washer between cone and locknut. The steel washer being the same colour as the locknut and cone, I can't tell from your photo 4 whether the washer is still there, but the aluminum spacer definitely is not.

So I would put that aluminum spacer back on the non-drive side. Reinstall the cogs. Look again at the relationship between the drive-side locknut and the cassette lockring: it will be so close to flush that you will think, "Nah, that'll never fit," but if you have 4 mm between *cog face* (not lockring) and locknut, you are according to spec.

Install your wheel and look again to see where the chain rubs. (Open the rear brake wide so you don't have to re-dish the wheel yet and can concentrate on watching the chain.) Since the hub was sound the way it was, the problem has to be in the frame. I confess to being very unsatisfied with this non-explanation but I think it's the best I can do without seeing the bike. At least we've established that there is nothing wrong with the hub (or at least, won't be, once you put the spacer back where it belongs.)

I think you should cold-set (i.e., "bend") the frame out to 130 mm, if for no other reason than you are going to be doing a lot of trial and error to get this right, and jamming the wheel into a too-narrow spacing over and over again is a pain in the butt for you, even if it doesn't hurt the frame any.

An earlier poster suggested using a 12T small cog. (I erroneously thought you were already using a 12T until I went back just now to re-read.) Would be an expensive fix, since you would not want to have a 14 -> 12 jump even if you could find an isolated 12T cog instead of buying a new 12-23 cassette.

Good luck.

Edit: If you really really have to, you could slip a very thin washer, say 0.5 mm, under the drive-side locknut to scratch out a tiny bit of extra clearance for the chain. This will affect the wheel dish if you are fussy, but probably won't weaken the wheel.