Another woman, Piper something I believe, has done a similar arrangement for hiking shoes. I know she posted here and on whiteblaze about it, maybe last winter?
Anyways, you can buy actual shoe soling materials online or from cobblers. Most common are soling sheets with just some texture, but Vibram does sell soles for their boots and (some?) shoes. Some examples here, though it looks like they won't sell direct. http://www.vibram.com/vibramrepair/catalogo.php?id_categoria=2&livello=1&lingua=2