You can, and I do.
It's not technically an Arduino anymore, I guess. I made my own board, replacing a resonator on a board will require some fine soldering, but it is definitely possible.
There are some gotchas: Anything time-related (e.g. millis() ) will be run faster than is should - 25% more millis() per second. Also, the bootloader expects 16mhz, so you won't be able to reprogram it at this speed. I purchased a USBASP programmer - it hooks into the 2x3 pin grid on one side of the board, and lets you reprogram it without the bootloader (this is how the bootloader is put on in the first place!). You will need at least 4.5 volts at 20mhz to avoid problems, compared to 3.78 volts for 16mhz - this means batteries will drain somewhat quicker (3x1.5v batteries will run down pretty quick), and if you have any motors or other draw on the batteries, 3 1.5v batteries will probably not work even if they are fresh.
Alternatively, going in the exact opposite direction, the lower the clock speed, the less voltage is required - for some projects, you might not need the clock speed - you can go down to 1.8v running at 4mhz.