I'll give you some advice, but the first thing you need to do is be aware that you're trying something that may well be beyond your abilities. .03 degrees (1/2 milliradian or 2 minutes of arc) requires a great deal of care, and probably access to a good machine shop.
In order:
1) You are correct to be leery of microstepping. It simply will not give you the accuracy you want. The article is quite correct.
2) A stepper with some sort of gearbox will work well. But you'll need a high-precision gearbox, and they don't come cheap. It will be difficult to find a gearbox which is made with your low-torque, low-speed, high-precision needs in mind. You have not specified your exact use, but keep in mind that if you do not require motion reversal during operation, your backlash requirements pretty much disappear. As wini_i has answered, a worm gear will work well, but be aware that mounting the gear requires considerable precision.
3) A motor with an encoder is possible, but there are a few problems. The biggest is that you need an encoder with at least twice the resolution of your system requirements. The difficulty with a digital encoder is that if the shaft starts to drift due to motor torque you won't know it until the encoder makes a step. It may then drift the other way until it makes a reverse step, etc. As a result, making a stable positioning system with such an encoder is extremely challenging, and a simple PID controller won't be adequate. Furthermore, trying to roll your own encoder from a device such as the AS5048 has a bunch of issues which the web site does not mention. Chief among these is the need to accurately position the center of the sensing area with respect to the center of the shaft. The higher the resolution, the greater the precision required.
4) A stepper with an encoder sounds good, but it cannot compensate for some mechanical errors. Specifically, it cannot help with backlash problems. The most likely result of such a system is that it constantly hunts between two mechanical shaft positions. Compensating for microstepping errors is (sort of, maybe) possible, but bearing friction and stiction may give results remarkably like gear backlash.
5) Other? Well, maybe. Perhaps your system does not need to actually step. How about if it turns very slowly and precisely? In this case you don't need a position loop, but rather a velocity loop with velocity derived from an incremental encoder (cheaper by far than a parallel encoder). In principle you could use a dial mounted directly to a motor shaft, but make a fairly massive dial whose inertia would compensate for disturbances such as bearing irregularities or motor glitches.
But let's stick with a geared stepper. I'm inclined to agree with Daniel that your best bet is a timing belt/timing gear setup. With a few cautions. You'll want as fine a timing belt gear pitch as possible, preferably an MXL series. Your .03 degree resolution gives 12,000 steps per revolution, which says you need a 60:1 reduction with a 1.8 degree stepper. This is a problem. If the motor pulley has 10 teeth, the dial needs a 600 tooth pulley, and you're not going to find one of those. You'll need to try one of two approaches. Either use a two-step reduction, or try something like a x8 microstep followed by a 7.5:1 reduction. A x8 microstep gives motor steps of (nominally) 12.5% of normal, and if the motor has 5% accuracy you should be all right. You'll also need to take pains to keep the belt tension constant to reduce play in the system. You'll need to make a good stiff mounting for the motor and dial, which is where a good machine shop comes in. Depending on what's attached to the dial, getting the dial perfectly centered on the shaft will be important too. The fact that your load torque is very low will help a great deal.
