Exhale on alternating footfalls. If you begin exhalation on your right foot, time your breathing so your next exhalation begins on your left foot.
Laura's father, Dr. Masi, taught me this technique. He's an accomplished marathon runner, consistently placing in his age group (early 60's) — 3:21:21 in the most recent Boston Marathon.
A natural asymmetrical rhythm develops as your body extends breathing for the extra beat. Instead of moving in 4/4 you are now moving in odd time signatures...with direct application to music:
L/B > R > L > R/B = 3/4 time
L/B > R > L > R > L > R/B = 5/4 time
L/B > R > L > R > L > R > L > R/B = 7/8 time
I find myself mostly running in 5/4 time, using 3/4 time for intense uphills, and 7/8 time for coasting or downhills.
After the first three or four practice runs, my body has begun to seek out asymmetrical breathing, replacing the previous even footfall habit. I would describe the feeling as 'unlocking' my body, as my diaphragm muscle decouples from my legs, and additional oxygen becomes available. Definite improved endurance.
Seems to be strong potential for teaching your body to play music in odd time signatures. All else follows breath.