I just discovered simavr, which is an open-source software simulator for AVR microcontrollers. It is a library which simulates a variety of AVR cores, and has hooks through which you can emulate hardware (such as devices attached to I/O pins). The idea is you write a C program which defines your hook functions, and then call into the library to run the actual simulation.
I was able to get a "blinking LED" program working in a couple hours by adapting the example code. I used ANSI control sequences to visualize the pins of an output port, but you can use any kind of UI you want. It looks as though simavr supports debugging of the target firmware using gdb, which is totally awesome. I will try that next.