Hall effect device for circa 1 tesla gaussmeter
There are a number of options. Whether any of them are practical will depend on physically what situation you want to measure.

It's true that most commercial Hall effect sensors use low fields. I haven't been able to find any high field ones with a quick google, which isn't to say they don't exist, just aren't offered to hobby users.

High field won't damage a Hall sensor, so you could attempt to calibrate the saturation region. I would expect that drift uncertainty would degrade any remaining sense of accuracy, but it may be worth a try, if you can figure out a trustworthy method of getting a strong, known, field.

If you knew the field direction, then using a sensor off axis would result in a smaller on axis (measured) component. Using two sensors on slightly different axes, and rotating the assembly until they both gave the same magnitude output, would line up the strong field between their axes, so automatically ensure that the field to sensor axis was at an angle of half of the sensors' mutual angle.

The Old Skool way of doing this depends on movement, the Integrating Fluxmeter. A coil is placed in the part of the field that needs to be measured, and is then removed to a large distance, where the flux is negligible. The voltage that the coil generates is integrated during the removal process by a 'capacitor wrapped round an op-amp' integrator. The voltage on the output of the op-amp represents the change of flux at any time. The coil removal does not have to be done at any speed, as long as it is fast enough for the integrator. With a low input bias op-amp, TL071 for instance, you should be able to use many seconds.

While the movement may seen to be a disadvantage, if you have a bench-top instrument with a probe, there are times when you'd want to put the probe into this gap, or that gap, employing the very movement you would need to make the measurement. How do you find a zero flux region? Turn the probe over and watch the integration output, it if changes, there is significant flux, and you need to go further away from your magnets. 

The calibration of an integrating fluxmeter depends on the coil area, the number of turns, and the value of the capacitor used in the integrator. You could work it out from first principles, or calibrate it against a Hall sensor. Ideally, you'd do both and compare them.

While it's true that wrapping the sensor in ferrite or iron would reduce the field it sees, I can't think of any practical way to make such an arrangement remotely calibratable or linear.