The practice to remove shoes (and other parts of clothing) in various circumstances seems to permeate throughout ancient cultures. Even with a liberal dating of Exodus around 700 BC, that still places the practice as very old among the Jewish people. Various reasons given include respect and hygene:
It was a custom for a person to remove their shoes as a mark of respect when approaching a Nazarene, or a place where a Nazarene lived or was buried. The practice primarily related to hygene rules.
The Bible, The Hallowed Book of Man - Robert George Crosbie
Other sources: Why are sandals considered to be unholy? and Was removing one's shoes a special sign of respect?
To date the practice before Moses, we'd need an older Jewish instance, but they seem hard to find, including the absence in any earlier Biblical stories (both in real dating and chronology). Jews in general believe that the practice was taught to Moses and was not known (at least to them) before that time. For example:
[T]he Jewish custom that requires mourners who at the conclusion of a funeral to remove their shoes in the graveyard as they depart the palce of burial ... undeniably echoes Jewish behavior on hallowed ground. This is a practice that God taught Moses when he warned him to "take off your shoes from your feet ..."
When a Jew Dies - Samuel C. Heilman
However, Egyptians removed their shoes when entering their temples, and the story tells us that Moses was raised as a prince by Egyptians, so he should have had much contact with Egyptian priests.
[Egyptian] priests wore papyrus or palm leaf sandals made so that they could be slipped on from the front or rear. Egyptian priests removed their shoes out of respect for their gods. It was also the custom to remove sandals in the presence of superior rank . Shoes were worn outside the house but never in the home.
History of Sandals - "Egyptian Sandals"
This seems to me, if we believe Exodus accurately describes Moses' life, strong evidence that Moses was keenly aware of removing foot ware for many reasons, including religious ones.
The burial of one's own dead in a place in effect turns that place into one's family's hallowed ground on which those who mourn must remove their shoes ... Death numinously transforms these places so that they are no longer profane and are set apart from the rest of the world. These places then serve, as we have seen, as special portals for petitions to heaven, places where the bond connecting mourners, the dead, and God are ritually reenacted and affirmed.
When a Jew Dies - Samuel C. Heilman
While searching for sources, I found this concept of transformation of the profane into something holy, merely because something divine has happened, opened a few doors for some interesting cultural explanations that do not exist in our modern society. It would seem that the idea that a "divine touch" makes things holy, therefore makes them no longer usable in common use. God touched the ground where the burning bush was, making it holy, but had Moses' shoes then touched that ground, they would also have been made holy and it would then be a blasphemy to use them in common vulgarities.
[I]t was common practice in many cultures to remove their shoes when walking on sacred ground lest their sandals become transformed. Contact with hallowed ground would have made their shoes unusable for everyday living. Priests and other individuals, who regularly were exposed to the divine, often wore special garments that were reserved for that purpose.
Göbekli Tepe: The Burying Of An Ancient Megalithic Site - Dr. Rita Louise
The author continues, discussing a different culture but contemporary to Moses', and notes that ancient peoples feared unintentionally making things holy:
A god, or his human counterpart, could not be touched; his possessions could not be handled. Likewise, if he touched you or something that belonged to you, its status was instantly changed. The rules of taboo included their home and anything in it. If a divine agent entered someone’s home, their home became sanctified and no one else could go into it or use it. Even the ground a divinity walked upon was deemed holy. Their fear of unintentionally coming into contact with something sacred was so powerful that it became custom in many regions to carry the god-king upon a littler so his feet did not touch the ground.
I can't help but reminded of the strict "no touch" rule of the Ark of the Covenant in this instance. I suspect that Moses had many ideas and images about removal of foot ware and some of them may have included ideas such as the above.