Don't quote me on this but you may be able to do a black zinc plating on brass, but this may require an undercoat plating which would drive the cost up. I guess we should ask, how much are you willing to spend? Most plating shops have steep minimums and less and less are willing to work with the public. What would be wrong with painting or powder coating the heads (visible areas?) the nickel on the thread should provide corrosion resistance....

I mentioned black nickel earlier, but I guess I should have said it is neither cheap or readily available. Sorry 'bout that.

Another option ould be to have the screws made out of stainless material and then black oxide coated, but you really want to keep oil on black oxide to keep it nice and this isnt always desirable. Yet another option: Replace the screws with a zinc plated steel screw (assuming it is a standard screw and the difference in material would be acceptable), strip the zinc (this is easy) and send for black zinc, parkerizing or so on.