Я не знаю как по функционалу будут ножны (никогда не делал), а вообще можно и без покраски хорошо обувным воском пропитать, если бесцветным, то сохранится естественный цвет кожи, только потемнее станет.
По поводу красок, то есть морилки на водной основе. Так же можно использовать красители для тканей.
Поищите, где-то здесь на форуме темка была о покраске кожи, там много рецептов и про окраску натуральными отварами тоже.