Hall effect sensors are so tiny you can put them almost anywhere. Counting the bolt heads on a drive shaft or brake disc is very easy.
You could put a sensor inside the speedometer itself. In that case I would use a QRE113 optical sensor and paint a black or white line on the spinning disc.