I've used a shellac & pigment paint on sinew-backed bows. Hide glue will work, of course, but you'll have to seal it with something waterproof. Shellac is a good paint binder and a good sealer at the same time.
With that said, hide glue has been used as a binder for paints for thousands of years. If you want something truly primitive, go with the hide glue. The only thing I would suggest is to use pigments or dyes that are not gritty. Crushed charcoal is gritty but soot (lamp black) works much better. You can also dye the glue with a natural, water based dye like beet juice, grape juice, cool-aid, etc.