Using an accelerometer is the only thing I can think of, if you can't use encoders (the double integral of acceleration will give you position).
I haven't used an accelerometer for that purpose yet, but my guess is that the error in trying to intergrate on a microcontroller, plus and any drift or offest in the sensor (integrating a constant will give you and unbounded error) is unlike to result in a very accurate position infomation consistently. There was an article in servo magazine (April 2007), doing this and was accurate to within 10-15%. Which is less accurate than your open loop method, so no use for you I guess. I don't see anyway of using your IR scanner.
Maybe someone else will have a suggestion, but I think Hexapods are just not as suited to dead reckoning/mapping, as a differential drive robot.
David