How to repair rusted welds

[yahoo12345]

I have a project with an exterior deck with beams and columns constructed of painted carbon steel. All of the welds are heavily rusted. I'm thinking of grinding out the old welds and rewelding, then apply a zinc repair coating over the welds. I would love to get your opinions on this idea or does anyone see better ways to repair the rusted welds? Also I would love to get recommendations on a good paint/coating to recoat the steel members. Rust damage is apparent at areas where paint came off. Thanks in advance!