One of several we marched to back in the '60s went

You had a good home but you LEFT
(You're RIGHT)
You had a good home but you LEFT
(You're RIGHT)
Sound off
1, 2
Sound off
3, 4
Bring it on down
1, 2, 3, 4
(shouted) 1, 2

with the left foot hitting the ground on the odd numbers. Marching starts, of course, on the left foot.

My GG Aunt said that her father used to sing "Hay foot, Straw foot, Any foot at all..." from his Civil War days. And THAT goes back to the Revolutionary War, when hay was tied to the left foot and straw to the right so that the soldiers could tell their right from their left -- or so the story goes.