My tank was almost as bad. I used a mix of gravel and a couple of handfuls of old nuts and bolts. Hung it with bungees on a frame and shook it for a few minutes at a time, and repeated many, many, many times, and turned it over and over, during the course of a week. The loose stuff came out but the surface was not shiney-clean by any means. Washed it multiple times with gas, and then had it steam cleaned at a local radiator shop.
The gravel I used was tan pea gravel and it seemed to wear some and produce powder that was hard to clean out. Next time, I will use limestone gravel, or just the nuts and bolts
I did not coat internally it; there have been coating problems long term in some applications and i just did not want to mess with that. So far, so good (about 500 miles, < 1 year). The high pressure FI pump straight off of ther tank has not croaked from rust or anything (yet).