If you're looking for a permanent solution that won't rub off to darken your shiny brass, good luck. None of the solutions recommended here will survive heavy wear and tear. Polish it hard and it will get shiny again. That said, you can get a really nice patina using any of them. Or just take it out and shoot it a lot and the brass will gradually tarnish. Honest wear will give you the patina you are looking for.