The guys on the knifemaking side of crafts all seem to use shoe
leather dye, then seal it.

I have seen some really nice work with this technique and apparently
the coloring lasts really well, too.

Robert