This may blow your mind, but it will work so well you'll just have to try it to believe it. Get thyse'f some Fiebing's leather stain. It will successfully stain over a finished gun stock (or any other piece of wood or leather). A bottle runs $5-10, and would do dozens of stocks, pistol grips, knife handles, etc.
You can find it at some old timey shoe shops that repair leather shoes, or order if from a knife makers supply or leather working supply house, like Tandy.
You might order a few different shades, darker and lighter, but make sure it's the Fiebings. Some of the new wonder finishes don't cover over wood for some reason. You can apply the stuff with the little dobber that comes with it, a cotton ball, or clean rag.
If it gets on yer fingers, it will still be on yer fingers come Sunday. Wear gloves if you don't want to show up t' church with red/brown fingers! It also accidentally stains the kitchen table, carpet, linoleum, and lots of other things the Mrs. may not want stained to match your gun stock. Be warned!
PS-you can use the black stain to very nicely darken matte, sand blasted, or frosted looking stainless. It won't stick to polished stainless, but it will permanently stain about anything else.