Is there is any material for an engineered structure or set of systems that will resist oxidation for the many thousands of years required for the journey?
Aluminum, when in contact with oxygen, forms a thin layer of oxide which protects the underlying metal from further oxidation. Moreover, aluminum has a more favorable elasticity to density ratio when compared to iron, so it is already preferred for applications where weight is a concern (yes, aerospace is such an application)
The only way to overcome these problems would be to have a large number of spare de-oxygenated ships in tow to move into.
False. Fatigued metal can be recovered by a proper thermal cycle. You just need some spare part and a thermal cycling facility.