Was Foot Washing a regular practice in early Christianity?
The short answer seems to be no!
I am sure some Early Church Christian communities may have had some sort of foot washing ceremonies, but evidence is quite sparse on this particular subject matter.
However there existed a monastic tradition of doing so under St. Benedict. The Rule of St. Benedict directs that it should be performed every Saturday for all the community by him who exercised the office of cook for the week; while it was also enjoined that the abbot and the brethren were to wash the feet of those who were received as guests. This no longer is done in Benedictine monasteries, in part, I think because of modern sensitivities. Many visitors may feel uneasy with this monastic tradition!
Liturgically this started in the 7th century.
The liturgical washing of feet (if we can trust the negative evidence of our early records) seems only to have established itself in East and West at a comparatively late date. In 694 the Seventeenth Synod of Toledo commanded all bishops and priests in a position of superiority under pain of excommunication to wash the feet of those subject to them. The matter is also discussed by Amalarius and other liturgists of the ninth century. Whether the custom of holding this "maundy" (from "Mandatum novum do vobis", the first words of the initial Antiphon) on Maundy Thursday, developed out of the baptismal practice originally attached to that day does not seem quite clear, but it soon became an universal custom in cathedral and collegiate churches. In the latter half of the twelfth century the pope washed the feet of twelve sub-deacons after his Mass and of thirteen poor men after his dinner. The "Caeremoniale episcoporum" directs that the bishop is to wash the feet either of thirteen poor men or of thirteen of his canons. The prelate and his assistants are vested and the Gospel "Ante diem festum paschae" is ceremonially sung with incense and lights at the beginning of the function. Most of the sovereigns of Europe used also formerly to perform the maundy. The custom is still retained at the Austrian and Spanish courts. - Washing of Feet and Hands
Today we call the washing of feet, the Mandatum.
The washing of the feet in the Liturgy of Holy Thursday. In the revised ritual the washing of the feet takes placed after the Gospel, which narrates the same event at the Last Supper. The men who have been chosen are led to chairs prepared for them. Then the priest goes to each man, pours water over each one's feet, and dries them. Meanwhile the choir or congregation sings a number of antiphons from the appropriate Gospel account in St. John. The ceremony is called the mandatum because it was on the occasion of washing his disciples' feet that Christ gave us the new commandment (novum mandatum) to love one another as he has loved us (John 13:4-17).