Have a look at these, some are quite cheap http://www.ssec.honeywell.com/magnetic/products.html. For example the full 3 axis/I2C interface (it can give a 3D compass bearing) hmc5843 is only $20 here http://parts.digikey.com/1/parts/159...c-hmc5843.html
I something like that would be your best option, combined with the i2c to usb program above, or using one of the cheaper and simpler 2-axis magnetometers with a microcontroller that has an A/D converter (pic chips like that can cost about a dollar). Either option would probably be small enough that you could make it sit flush to the edge of the phone and attach via usb (so 3 axis would come in handy).