How can I execute MIPS assembly programs on an x86 linux?

You will need either a cross compilation toolchain, or to build your own cross binutils. For a prebuilt toolchain, you can visit code sourcery. If you just want to compile assembly, then all you need is binutils. There are some guidelines on the Linux Mips wiki

For the emulation part, QEmu would be my choice.

Incidentally, Spim does not require X Windows. It has a console interface as well. Run either spim or xspim.