How Do You All Paint Wood When the Nail Heads Are Rusting?

Use some rustoleum rust reformer spray on the nail heads and then paint the whole thing with a fence/barn paint.

You will not stop rust from coming through but the reformer will stop it a lot longer than not using it.
The fence & barn paint is meant for outdoor use and is pretty tough stuff and not too expensive.