I've made a few, they're all knit, so sorry if you're not a knitter, I guess this won't help!
There's a pattern for a baby slipper/shoe with a leather sole in the book, The Children's Year: Crafts and Clothes for Parents and Children to Make, by Stephanie Cooper. It's an excellent book to have anyway...but maybe you could get it from your library and just copy that pattern?
I've also made a pattern by Fiber Trends for slipper/clogs, and sewed the suede bottoms on. I really liked this pattern--it's knit and then felted. Here's a link to the pattern picture: http://www.fibertrends.com/viewer/V6_baby.html
You're local yarn store would probably carry these patterns.
For free patterns (the best, of course!), go to http://knitting.about.com/library/blkidssockspic.htm
for a list of a few patterns for socks/booties for kids.
Good luck, let us know what you end up doing!