Great news for a change!
Hall sensors and magnets work perfectly! No skipping, no delay, no need for debouncing. They are so precise I just placed two sensors next to each other and I can detect the change of direction with just one pass of a magnet...
I've placed eight magnets around the wheel (the glued encoder chart from the previous solution was quite useful for this

). I think I could do even sixteen, but for now this is good enough - the time between the pulses is below 100 ms, which is comparable to analog game controllers.
Funny thing is, I've almost had another solution - I've recovered an IR phototransistor and emitter from an old mouse and wanted to count the teeth on the wheel. I've got the wiring part all done when the magnets have arrived...
Anyway, thank you all for invaluable help, I've learned heaps doing this!