[Espadrilles][1] are made with only vegetable fibers

> Espadrilles (Spanish: alpargatas; Catalan: espardenya; Basque: espartinak), are casual, flat, but sometimes high-heeled shoes. They usually have a canvas or cotton fabric upper and a flexible sole made of esparto rope. The esparto rope sole is the defining characteristic of an espadrille; the uppers vary widely in style. 
>
> Esparto, halfah grass, or esparto grass is a fiber produced from two species of perennial grasses of north Africa and southern Europe. It is used for crafts, such as cords, basketry, and espadrilles. *Stipa tenacissima* and *Lygeum spartum* are the species used to produce esparto. 

[![a pair of espadrilles][2]][2]

Though in the past they were peasants shoes, your people can use a similar approach to manufacture their shoes. 

They might use vegetable fats to waterproof them.

Another approach is what Japanese do with their [geta][3]: wood and rope.

> Geta (下駄) are a form of traditional Japanese footwear that resemble clogs and flip-flops. They are a kind of sandal with an elevated wooden base held onto the foot with a fabric thong to keep the foot well above the ground. 

[![a pair of geta][4]][4]


  [1]: https://en.wikipedia.org/wiki/Espadrille
  [2]: https://i.sstatic.net/S7Rd4.jpg
  [3]: https://en.wikipedia.org/wiki/Geta_(footwear)
  [4]: https://i.sstatic.net/ZFS8r.jpg