Here are the soles of my boots, gooped up with glue that dries clear, works on fabric and rubber, is waterproof, and can be used for shoes. It took about 20 minutes to decide which glue to buy. I was not really sure how the Crayola Magic Sculpt would glue up with these stronger glues, but it seemed to do ok.
Here's something that looks like it's from Gulliver's Travels:
The bottoms of the soles are made from a thin cut up tire mat that my Gingher shears were able to slice through. I was going to glue leather but then somebody had reminded me that leather is not very sure footing on rugs...and I remember how scary it could be if your leather soles got wet and you walked on tiles. (It's so great to have a lot of mentors)!!