Originally posted by Geir Widar:
Steel wool is not the most brutal rust removal tool, to underexaggerate..
If this was my grill, I's give the original wheels a mild blast of sand, but that may be because I have access to compressed air as well the rest of the equipment needed.
I'd water sand the rods with let's say 600 grit paper, soaked for at least 12 hours. Soaking time is important!
A thin layer of some kind of rust stopping and preserving oil, after some polishing with the same grit after sand blasting, and the originals will be as good as new for many years with some maintenance.
Link to a very good preserving oil:
http://www.deksolje.com/