Optoelektronisch ist wegen der Verschmutzungsgefahr vielleicht keine so gute Idee. Ausser du baust eine extra Box mit einem extra Zahnrad geschützt auf.

Die Idee mit dem Magnet ankleben könnte klappen, oder du verlängerst eine Achse und legst einnen größeren Zahnrad drauf, was der Hallsensor auch ordentlich erkennt. Mit einem Schmitt-Trigger kannst du den Signal dann so aufbereiten, dass es für den uC eindeutig ist (also entweder 0V o. 5V).

Die Frequenzen zu erkennen sollte kein Problem sein, auch mit einer 8051 nicht. Vor allem wenn Du einen du den Frequenzeingang als einen externen Interrupt einbindest.