I would get an inexpensive accelerometer and figure out how to recognize the accelerations associated with a step. I'm certain it's pretty easy. You could probably home brew a shock sensor that could do the same for aless money. then it's justa matter of counting the steps.
gps will be more accurate but it will need to have frequent clear sight of the birds. obviously this won't work for a lot of indoor walking and you can forget caving...
and by the way, pedometers are dirt cheap these days - you can get a decent one for under $20.