Hypothetically speaking couldn't you collect it from any security camera in an area where you have positive ID on people? Airport security comes to mind.

With all the trade in personal data in the US I assume it's only a matter of time before places like grocery stores start selling it.

Why stop at just gait though? Geometric fingerprinting of various body parts is also possible. Palm geometry readers have been commonplace for a long time.