In Teensyduino, I implemented a Tools > CPU Speed menu. The crystal is always 16 MHz, but selecting something other than 16 (eg, 8, 4, 2, 1) reconfigures for that speed using the on-chip clock prescaler. Teensyduino has delayMicroseconds(), delay(), millis(), and micros() (and also extensions elapsedMillis and elapedMicros) that work at those 5 speeds. It also has speed-dependent initialization of the PWM and ADC clocks so they work as expected at all speeds.
Do don't need to buy a $16 Teensy to get this code (but of course, I wouldn't mind if you did... all this software development is funded by Teensy sales). The Teensyduino installer is a free download. After you run the installer, Teensyduino's core is placed in your Arduino, in hardware/teensy/cores/teensy (on a Mac, control-click and choose "show package contents"). Inside you can find this code, and probably even get much of it to compile and work pretty easily on an Arduino Uno. The delayMicroseconds() function, while built from a lot of optimized inline assembly, should be fairly self-contained and ought to work on any AVR chip.
The code in the IDE which implements the CPU Speed menu was contributed as a patch over 1 year ago. Sadly, it never was included in Arduino.http://code.google.com/p/arduino/issues/detail?id=257