well joe south wrote the song and ray stevens did a hit cover version of it. But I think originally it's a Native American saying, though not shoes of course.
As Dot suggests, most sources seem to indicate that the original phrase ("Don't judge a man until you have walked a mile in his boots") has its roots in an early American proverb, without any exact origin being known.
I have half a dozen books about the Native American Indians and one in particular, Illustrated Myths of native America by Tim McNeese I am sure includes the legend, but I can't just find it in there.