My good old Machinery's Handbook (19th ed.) lists recipes for coloring brass. The recipes for blackening brass include use of arsenic compounds (!) and potassium cyanide, both of which may be tough to find.
Another recipe uses: 8 oz "sugar of lead", 8 oz. hyposulfite, and 1 gallon of water. Immerse part in hot solution. They recommend overcoating with lacquer to prevent/retard fading. The black color is lead sulfide, so a lacquer coating just to keep the stuff from getting onto people's fingers might be a good idea. You might try using zinc sulfide and flame treatment too (somewhat safer).