Maybe you could still kinda stain it- heat and mix up some beeswax and charcoal powder. It won't work like normal stains, but it should transfer some color into the wood for you. You'll need to heat it as you use the dyed wax to keep it flowing, and hopefully that wood will accept some of it.
Also, just about any natural dye should work this way. Woad is blue, cochineal is red, ground up rust will give you a brown/orange. All of these should be fine with beeswax as well. I would not think any water soluble/hydrophilic dyes would work too well, so probably not Rit dye.
I have found quite a few natural-based dyes on Amazon, but you could just do an online search.
Mike