You can use rotary encoders, and wheels with a known diameter.
Use a number of IR LED beacons and a wiimote (used as an IR camera) and triangulate your position.
Accelerometers (and/or gyros), math and some luck.
I'm sure someone will have more and better ideas 
[edit]If you can, you could make a grid of the area using black and white tape (for instance) and a color sensor to detect a passing of a grid.
You could have black/white along X, and red/blue along y. Then, each time a state changes [x from black to white or vice versa] | [y from red to blue or vice versa] you simply increment the position by the width of the grid. [/edit]