Which one is correct?
Taking a snapshot-sample approach to this question, I ran a Google Books search for four phrases that incorporate "by foot" or "on foot": "travel on foot" (blue line, "travel by foot" (red line), "traveling on foot" (green line, and "traveling by foot" (yellow line). Here is the resulting Ngram chart for the years 1840–2005:
As this chart indicates, all four expressions have been in use in published writing for many years, but the "on foot" wordings are at least somewhat more common than the "by foot" alternatives. The chart also shows that the frequency of occurrence of "travel on foot" in print has declined gradually over the past 150 years, while the frequency of travel by foot" has increased slightly; the difference in frequency used to be much greater than it is today.
Historically, "travel/traveling on foot" goes back much farther than "travel/traveling by foot." The earliest match for "travel on foot" in a Google Books search is from Alexander Grosse, Sweet and Soule-Perswading Inducements Leading Unto Christ (1632):
Euery man may see in these times mens naturall lusts and affections which should like servants be kept under and suppressed, humbled, brought low, and made to walke on foot ; yet these are set on horsebacke, exalted, honoured, preferred, and Christ the Prince of peace, and all his ordinances, statutes, and testimonies, which should reigne and rule like Princes in the soule of man, these are made like servants to travell on foot ; these are of no esteeme and price With men ; these have no rule and sway in the hearts of men : ...
The earliest Google Books instance of "travelling on foot" is from only a few years later. From Samuel Purchas, A Theatre of Politicall Flying-Insects (1657):
At such times [as during a plague of locusts] the people depart from their own Country, so that wee have found all the wayes full of men and women, travelling on foot with their children in their arms, and upon their heads, going into other Countries, where they might finde food, which was a pitiful thing to behold.
In contrast, the first Google Books match for "travel by foot" is from more than 200 years after the first match for "travell on foot." From Missionary Herald (April 1836):
We met with very good and attentive congregations at nearly all the places [in the vicinity of Byamvillee, Ceylon]. We were obliged to travel by foot through roads which are impervious to every other mode of travelling.
And the earliest Google Books instance of "travelling by foot" is from "Railways in India," in The Artizan (June 1847):
The average cost of travelling is, to 1st class passengers, 8d. per mile each ; to 2nd class, 1.12d. per mile each ; and to 3rd class, 0.6d. per mile each, including food if proceeding by water, and 0.533d. per mile each, including time and food if travelling by foot.
Nevertheless, both forms have been in attested use for more than 175 years. To judge from the Google Books search results, "travel/traveling on foot" is considerably older and continues to be more common than "travel/traveling by foot"; but both are currently in use and—by any reasonable standard of appraisal—are "correct."
It occurred to me that the original preference for "on foot" might have influenced by the then-common alternative transportation mode "on horseback," given that the phrase "by horseback" sounds extremely odd. However, both terms are so old that both seem to have been in place by the time the earliest Google Books volumes were published—and as a result, there is no clear basis for supposing that adoption of one of those wordings influenced adoption of the other.
Are there instances when the expression 'by foot' is preferred?
Looking through the matches for "travel/travelling by foot," I found a few examples where "by foot" sounds better (to me) than it usually does. The 1847 example of "traveling by foot" cited above is one such instance—and the reason it sounds better than usual, I think, is that it appears in parallel with the earlier phrase "proceeding by water." An even stronger example appears in Christopher Froelich, The Complete Idiot's Guide to Learning Russian (2004):
Russian verbs of motion sometimes cause problems for English speakers for two reasons. First, motion verbs come in pairs of definite and indefinite motion. ... Second, Russian does not have a verb that means "to go." Instead, verbs of motion in Russian indicate the method of travel—by foot, by vehicle, by plane, by boat.
And stronger still is this instance from The Code of Federal Regulations of the United States of America (1983):
(g) Winter travel. The Superintendent may, by posting or notice, establish on the basis of weather and snow conditions, a winter travel season. During this season, registration with the Superintendent is required prior to any winter travel by foot, skis, snowshoes, or sleds, away from plowed roads.
It is easy to see in these last two examples how the other travel options (all explicitly or implicitly preceded by by) influenced the author's choice of "by foot" over "on foot." This preference is, however, a highly subjective one. Even more so, I suppose, is this one—from Systems Analysis in Forest Resources: Proceedings of the 2003 Symposium (2005) [combined snippets]—where again I can understand the author's inclination to go with "travel by foot":
This methodology required intensive attribution of equipment and travel routes, and in the context of forest road engineering, it was able to ignore the problem of off-road travel by foot.
Here "off-road travel" is one idea and "by foot" follows at a slight remove; perhaps the author wanted to avoid even the faintest shadow of the misreading "ignore the problem ... on foot"; certainly no such misreading is possible with the wording "ignore the problem ... by foot."
But even in these rather unusual instances where "by foot" is arguably a good choice, it doesn't follow that using "on foot" would be an error. The same goes in reverse for the usual case where "on foot" may seem more natural and idiomatic. Ultimately the choice between "travel by foot" and "travel on foot" is a matter of personal preference—one in which more people writing (and speaking, presumably) favor the latter more of the time; but I couldn't find any special travel-related usage of "by foot" in which replacing "by foot" with "on foot" would be idiomatically dubious.
Why is the singular noun, 'foot', used?
The idiom "on foot" goes back very far in English. Marlowe includes this exchange in Doctor Faustus (1592):
Mephistopheles. What, will you go on horse-back or on foot?
Faustus. Nay, till I'm past this fair and pleasant green, I'll walk on foot.
Even earlier is this instance of "on foot" (in the sense of "in the process of occurring" or, in other words, "afoot") from a letter by Secretary William Cecil, dated October 31, 1559, reprinted in The Works of John Knox, volume 3 (1853):
On the last of that month [October 1559], Cecil writes from Court, and says, "If Balnaves shuld come, it wold prove dangerous; and therefore it is thought better that he be forborne until the matter be better on foot."
I couldn't find any explanation in a reference work of why English prefers "on foot" to "on feet." But whatever the reason may have been, the decision on the preferred form happened long ago. (Merriam-Webster reports that afoot in the sense of "on foot" dates to the thirteenth century; and as there is no plural option afeet in this case, the early appearance of afoot suggests that the singular was already in place for "on foot" as well.)
by foot