[DonVoigt]

GT,
any abrasive will remove black oxide. It is only on the surface.
Baking soda is quite mild, but will still leave a matte finish.
Walnut shells come in different grades, and can be quite aggressive, more so even than glass beads!
Fine glass beads are a good option too; worn out glass beads are even better for some projects.

I have used sand, glass beads, zirconium oxide beads, and walnut shells myself; but not baking soda.
Baking soda would have the added benefit of completely washing away with water.