I presume that the entropy of the system should decrease during rusting of iron because the atmospheric oxygen gets converted to solid state from gaseous state which should result in the decrease of randomness. So am I correct?
It is necessary to differentiate between the change in system entropy and surrounding entropy.
Rusting involves a decrease in system entropy, but causes an even greater increase in the entropy of the surroundings. This is because it is an exothermic reaction, releasing heat energy to the surrounding molecules, increasing their disorder.
Overall, when you calculate total entropy (system entropy + surroundings entropy) you find an increase. Hence, the process in spontaneous.