I started to write a post to say how easy it is... then I thought better and did a search on the new '04 accord. Is
this what it looks like?! Holy cow, they really made it hard on you. My '02 accord is just a simple double din opening. I don't imagine there's any factory stereos that will fit in yours.
I wouldn't go so far as to say an iPod is the only way to go, though. If you got clever with your method of input to a computer, you could setup a carputer using one of the auxilary input interfaces that were refered to in the previous posts...
...and of course you could always rip out the whole dash and build up your own custom head-less mp3player. Look around the forums, there's tons of ideas to get!