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.