I was pleasantly surprised to discover that the parts necessary for an analog compass solution are available in off-the-shelf form.

Here's the idea.

0. Hold the device in landscape mode. World-facing camera is facing forward; user-facing camera is facing the user and is at the upper-left corner of the screen.
1. Place a periscope-like mirror on top of the user-facing camera. This directs the line-of-sight of the user-facing camera downwards. Such a periscope mirror, intended as a phone accessory, can be seen here, here, here and here.
2. Hold a miniature ball compass beneath the periscope mirror. Such a ball compass, intended as a phone accessory, can be seen here, here, and here.
3. Use image processing to capture the image of the ball compass and determine its orientation. Make this orientation available to other applications such as AR or mapping apps.

The merits of this approach are:
1. Cheap.
2. No power needed.
3. Relatively small: parts are originally intended for mobile phone use.
4. Graceful degradation. Just by having the analog compass available, you can manually look at your orientation and drag an on-screen compass to rotate a map or an AR display. With the mirror and the image processing, this could be automated, but automation is not strictly necessary.

I managed to find these parts in a local store, but you can probably order them over the web as well. Total cost was around $30.

The main technical hurdles to implementing an automated image-processing solution would be:
1. Sufficient lighting for the camera to recognize the compass. A small battery-powered LED might work.
2. The ability to use both cameras at the same time (world-facing camera and user-facing camera). Unknown if the hardware supports this.
3. Mechanical: some kind of a bracket to hold the mirror and the ball compass in place.

Given the difficulties posed by a real digital compass solution (tiny parts making for difficult soldering, high cost, external battery, lack of USB host), the analog solution seems to be an alternative, at least for people like me without skills in surface-mount soldering.

At least, buying these parts gave me something to do while I wait for the N900 to become available