Detecting position -- Hall effect sensor?
I've used the Allegro 3503 ratiometric linear sensor.  It's discontinued, but I suspect its similar to the 1301/1302 sensors.  It is very linear when positioned between two opposing magnets.  This particular config (push-push mode) is shown on page 27 of the guide that you can download at http://www.allegromicro.com/en/Design-Center/Technical-Documents/Hall-Effect-Sensor-IC-Publications/Hall-Effect-IC-Application-Guide.aspx, 
 but there are some other interesting modes. Give that ref a good read.  You are talking mm here, and not cm.  I think if you have a small 1 mm range, you can probably get 0.5 mm resolution, but I can't say I've pushed it that far.  Strong neodymium magnets would certainly help.

They're even easier to use than you describe.  The output voltage simply changes as a function of flux density.

As a design alternative, you might consider an optical position sensitive detector from Hamamatsu.  You'd just need a 1-D sensor.  They're good to about 50 microns over two millimeters.