Black rocks really makes a big difference. See the pic below from Ledobe showing the before and after impact of BR on her amethyst Bridgit:
http://forum.purseblog.com/coach-clubhouse/coach-rehab-and-rescue-club-624452-371.html#post22705588
I like Wenol as a metal polish, I buy it on ebay (see link below, nma)
http://www.ebay.com/itm/Red-Wenol-M...520?pt=LH_DefaultDomain_0&hash=item41712b5d10
But a lot of people like to use Brasso and you can get it at any hardware store and probably at the grocery store, too! You will need lots of cotton Q-tips and soft rags and be prepared to do a lot of rubbing! I hate cleaning brasses but it really makes a big difference.
I know that it seems like you have to buy a lot of supplies to rehab a "bargain bag" but you will only use a small amount on the bag and you can use the same supplies on other rehabs and household goods.
How is the edging on the strap, is it worn away and faded? I would get a small bottle of paint (very inexpensive) at the hobby or craft store and an artist's paint brush to touch up the edging. After 24 hours it is permanent. Some rehabbers prefer to use leather dressing for the edges and they use products called Edge Kote and Edge Coat that you can find online.
The bag is looking great and it will soon look spectacular!