Probably a bit much to deal with everyday, but - what about a line of shoes that have varying heights, angles and weights? Or even a single pair of high-tech shoes that automatically randomize these elements every 24 hours.
You're probably better off just throwing a pebble or two at random spots in your shoe. Random height/angles are most likely going to fuck with your joints and just make it too hard to move efficiently, while a pebble or two will be annoying but tolerable and should be enough to change your gait up.
I remember in the Bourne Identity (book), the main character puts a rock in his shoe, which forced him to change his gait to not be noticed by surveillance. I wouldn't be surprised if something like that were effective in real life.
I imagine these would wreak havoc on your joints though.