OK, here's how it ended up for me.
I registered my original Fire back to my account, immediately got the 500 coins, and, surprisingly, another free month of Amazon Prime. Hehe. I love Amazon.
I called support again to confirm that I'd be able to keep the coins even I removed the Fire from my account. They said I would, and so I did, and indeed the coins stayed.
Support also pointed out that the coin option and balance is now visible from the regular Amazon web site, not just from the device. Go to amazon.com and browse to any paid app, and look at the payment options on the right. If you have enough coins to buy the app, you should see something like:
ApK