Building a treadmill speed sensor
There is almost certainly some part of the motor mechanism that is accessible and which can be used to return a periodic signal. This could be eg 


a rotating shaft with a "bump that will trigger a magnet plus Hall sensor, 
or  the flywheel on the motor which will probably have some part which differs enough to trigger a sensor. 
or the flywheel surface can be given a white soot of paint etc or a strip of reflective tape to trigger an optical pickup.


You can buy optical tachometers which will repond happily to a periodically varying surface and the silvered tape trick is a standard one with them.

Some of the available tachometers will have some form of output (RS232?) or will be more acceptably hackable than the treadmill. 



OR you could build your own without too much effort:

DIY Optical Tachometer

Another home made optical tachometer 
 More complex crcuit than is needed but the front end gives ideas. 



This (from above) plus an Arduino is about enough - or just the sensor with care. 





Arduino in the sky with clothespegs - actually a really simple optical interface optical tachometer with Arduino based optical tachometer with numerous clothes pegs assisting.





Wow !!! - Vast list or Arduino application with link to above project (at least)

Sample of commercial unit - Australian seller $A80 rtail. I have one of these. Goes OK. No external interface. Hackable.



Identical unit at Farnell UK 43 GBP ;-(.

A zillion possible references