How "western" are we talking about? Indians on the west coast, living next to the ocean, had more pigments available than those in the midwest, for example.
An ancient recipe for black paint can be made with ash (from burned grass) mixed with blood. Of course, blood can be used as-is for red/brown paint. Egg yolk can be applied straight as yellow paint.
Fresh leaves can be crushed and smeared onto the wood for a light green stain (but it will fade if left in the sun). Certain roots or berries can be crushed and applied, as a stain, in a similar way.
I use shellac as a binder for all my natural paints but there other options. If you're patient and a glutton for punishment, you can use pine rosin as a binder...just heat it up and mix in your favorite dry pigment. You'll have to keep the work piece warm while you're painting but the paint will be waterproof when it cools.
Hide glue has been used as a binder for water color paints for as long as pottery has allowed people to boil water..... and was used often by Native Americans.
For pigments, I order mine on-line from art supply stores.
Hope that helps.