Most Hall sensors rely on a metal toothed wheel (or similar) and static magnet to generate a variation that is measured.
See: http://en.wikipedia.org/wiki/Hall_effectSo moving the sensor as you suggest is worth a try.