The way to get the most energy from walking probably would be with a permanent magnet and coil. Have a strong cylindrical magnet (rare earth type) suspended by two weak springs inside a coil with many turns of fine wire so that the magnet moves up and down through the coil when you walk. You would tune the magnet and spring to have a resonant frequency near the normal walking pace to transfer the most energy and probably mount the assembly more or less vertical to detect the up and down walking motion. The AC current from the coil could then be rectified to dc (with Schottky diodes for good efficiency). For maximum efficiency you would probably also want to use a switching regulator to generate the proper charging current to the battery.
The required size of the magnet, the number of coil turns, and the spring tension would likely need to be determined by experiment. The magnet should fit as snuggly as possible in the coil without rubbing for best energy transfer.