IN small robots, with present day technology, lots of things get sacrificed when making tiny robots...perhaps you have to make one here. How accurate do you need leg positioning? It is more likely that you just need to know when the joint has reached it's rotational boundaries. Perhaps a switch on each extreme of the joint so that the robot just knows when to stop or reverse motor direction- just enough to be able to walk. You won't have fine motor control, but it may be a sacrifice you have to make.
How small a pot do you need? This is 1cm, 10 thousand cycles pot:
**broken link removed**
Try looking at specialty manufacturers like Vishay instead of general suppliers like Digikey. Probably not as cheap as you would like though and you may need to get it from the manufacturer (Vishay tells me they sell direct in low quantities for many items, you probably need a few anyways depending on how many DOF your legs have.)
Here are some FAR OUTdeas:
Ever heard of fiber optic whiskers? Read up on it...Now that you have read about it, perhaps you can go beyond simply determining whether or not the photo-sensor output is "not normal" as is used in crash detection...just maybe, just maybe perhaps the readings from the photo-receiver roughly indicate the joint's position...Oh yeah, fiber optic wire might not be able to bend as sharply as you would like it to...but it's a start. Perhaps you can mount the fiber in an unconventional position with respect to the join.
Perhaps you can find a tiny resistive flex sensor. This would save you BUTTLOADS of space and would be the perfect solution...if you can get it to work. Actually, it's really easy to get it to work. You just need to form a resistive divdier with the a fixed resistor and the flex resistor across the uC power supply and read it with an ADC. THe hardest part by far is finding a flex sensor that small. I have only ever seen one kind for sale no matter where I look...and it's pretty big.
Maybe use conductive foam at the joint to form a pressure sensor that change resistance as the leg bends to compress the foam thereby changing resistance...although it seems very little foam would be used because of the joint size and force from the mtor required for compression of the foam. The small amount of foam used may make it only have very small resistance changes.
You might notice all these ideas have less to do with the motor position and more to do with the position of the actual leg...mainly because I can't think of anything simple and small enough to work with a tiny motor.