Change switched outlet to ceiling fan and unswitched outlet
You can just cap off each end of the unused red wire; there's no code issue with leaving it in place (see Q1/A1 here). If you later change your mind or want to have the switch also control the outlet/something else, you'll be glad you didn't remove it.

The rest of your plan looks reasonable, though if I understand it correctly -- you're intercepting the run between the outlet and the switch, which runs through the attic, to install your fan? -- the logistics of splicing in the box for your fan might be tricky. Though, since you're already up in the attic, you could pull a new 4-wire between the switch and the ceiling fan box; that'd also give you the option to install a fan with a separately-switched light fixture.