I would prefer to do this as a comment to pericynthion's answer, but it will be (much) too long. You have said that "I don't really get how to implement what you suggest, neither how that would allow me to precisely verify that my measurement (with the Hall effect captor) precision is 0.5° or better."
You understand, I hope, that you will need a framework to couple the sensor you have chosen to the shaft of whatever motor you finally use. Attached to the end of the shaft will be a magnet which is positioned above (or below) the sensor. You will need to fabricate a PC board to hold the sensor and make connections to it, and if you're having trouble swallowing the $20 price of a precision servo, you're in for a bad shock. All you get for the sensor is a TSSOP IC. In principle, you can take a piece of wood, mount the IC to it with a dab of epoxy and run very fine (like 30 AWG) wires to it, but you will find some real problems with this approach. First, soldering the wires for such fine leads takes real skill, so you'll need someone who knows how to do it. Second, the wires themselves must be secured so that you don't accidentally rip the leads off your sensor (hint - more epoxy). Third (but hardly least) this will make providing a good ground very difficult, and you NEED a good ground. Finally, you need to have the sensor positioned so that you know where its center is within 0.25 mm - see the data sheet. Let's assume that you have done all of this, and have a mounted sensor which is connected to power and readout electronics.
Now make a framework which holds the sensor in place, and also provides a shaft with a magnet suspended just above the sensor, with the shaft free to rotate. For purposes of discussion, let's assume the shaft is 6 mm in diameter. And remember, the center of the magnet must be aligned with the center of the sensor chip to .25 mm or better.
Take a small block of wood, about 50 mm on a side. In the center of one face, drill a hole the size of the shaft. In the center of another face, drill a hole all the way through, the size of a laser pointer.
Slide the block onto the shaft, but not far enough that the shaft protrudes into the other hole. A dab of glue will keep it in place. The result should be a block attached to the sensor shaft, with the shaft and block free to rotate.
Now slide the laser pointer into the second hole, and adjust it until it is centered in the block. Turn on the laser, and rotate the block until it is pointing at a convenient spot on a wall. Interrogate the sensor, and determine the current shaft angle. Now rotate the shaft so as to move the spot a convenient amount. Measure the amount the spot moved, and again read the sensor to get a second shaft angle reading.
Knowing the distance from the pointer to the wall (actually, from the center of rotation of the pointer) and the amount the spot moved, you can calculate the angle the pointer moved, and compare this to what the sensor reported. From this you can determine the accuracy of the sensor.
For instance, let's say you have the sensor shaft level, 1 meter above the floor, with the axis of the shaft parallel with a wall 5 meters away, and the spot on the wall 1 meter above the floor. If you rotate the shaft so that the spot moves 1 meter vertically, you know the shaft had to rotate 11.31 degrees, since the tangent of 11.31 degrees is 0.2, and so is 1 divided by 5. From this you can calculate how many bits of angle change the sensor should report.