Another thought is having them powdercoated. They will take your funky wheel, sandblast it, powder coat it and hand it back to you like it was new for a decent price when you count in the cost of paint and all that you would pay to do it yourself. Not always a way to go of course being you may not have a decent powder coater around. I have access to quite a few and a few are CRAZY over priced. So if that is the type you have available to you sand blasting, epoxy primer and paint as Ray said would be the best way to go.
But call around and see, I had one a few years ago that did a set of wheels for $125, sand blasting and all.