We demonstrate a novel concept for operating graphene-based Hall sensors using an alternating current (AC) modulated gate voltage, which provides three important advantages compared to Hall sensors under static operation: 1) The sensor sensitivity can be doubled by utilizing both n- and p-type conductance. 2) A static magnetic field can be read out at frequencies in the kHz range, where the 1/f noise is lower compared to the static case. 3) The off-set voltage in the Hall signal can be reduced. This significantly increases the signal-to-noise ratio compared to Hall sensors without a gate electrode. A minimal detectable magnetic field Bmin down to 290 nT/sqrt(Hz) and sensitivity up to 0.55 V/VT was found for Hall sensors fabricated on flexible foil. This clearly outperforms state-of-the-art flexible Hall sensors and is comparable to the values obtained by the best rigid III/V semiconductor Hall sensors.