The commercially available hall sensors are so small that they do not give good sensitivity compared to inductors. If you were to use an magnetic antenna, made of magnetic material, that might improve the sensitivity by effectively increasing the sensor area. A long iron rod with a gap in the middle, and the sensor placed in that gap could be an example of such an antenna.
I would think that an air core inductor driving a dead short (such the input of a transimpedance amplfier) could give a pretty wide bandwidth, mostly limited by the Q of the inductor and the loop gain of the amplifier.
A variation on this idea is the subject of U.S. patent 5,296,866. Perhaps you would want to download a copy from Google Patents and have a look at the circuit.
Google Patents
You could place use three small loops, one for each axis as used by Combinova in their magnetic field meter. The outputs from the preamp for each loop could either be combined (the output being the square root of the sum of the squares of the outputs from each axis) to provide total magnetic field or they could be used separately.
**broken link removed**
(Photo above by Combinova)