It sounds like a great idea; the character backstory happily justifies such an unusual companion. I don't think you should worry about finding a particular character build to make it viable, just bend the rules a little.
Although there's certainly a balance issue to consier, the DM can easily balance things by ensuring the rust monter is a recalcitrant little bugger, a serial devourer of fellow PCs armour or utterly cowardly in battle (yet eager to snuffle up the broken arms and armour once the dust has settled). As the PCs progress in level, you can hand over more control to the player.
I'd imagine the recalcitrant little bugger would happily charge an armed and armoured fighter, the more exotic metal he carries the better. Though a kid with a stick would make it scamper away and hide.
I wonder if it would be smart enough to realize what sorts of metals (everbright, artifacts, etc) are indigestible, at least after encountering them before. I wonder if you could hold the creature at bay by just dropping something metal (like an armoured opponent) and a handful of colourful coins in a nice quiet place away from the fighting. It's not like a rust monster has an insatiable appetite for more metal than it can eat at once.