In Cory Doctorow's book Little Brother, the protagonist defeats gait sensors with some pebbles in his shoe. It's really not such a bad idea, as every step is going to be different as your foot tries not to hit the pebble too hard.

Do you have a database of walking styles? Does anybody?

They definitely have access to most people's photos - driver's licenses, passports.

I personally don't care if they know where I go in public. They can just tail me if they really want to know.