Mplayer has many video output drivers available and though half of them can only be used under X11, there are quite a few that give good results without the need for an x-server. You can see what video output drivers you have enabled by typing (at a terminal):
mplayer -vo help
I have the default installation from Ubuntu, so I have quite a lot of drivers installed, and can use them without any further trouble. If you compiled from code, you may need to have enabled them then.

So here are the drivers I tried out:

• Framebuffer device drivers: fbdev and fbdev2. Use mplayer -vo fbdev filename or mplayer -vo fbdev2 filename .
• SDL: SDL probably gives the best results of them all, but doing it in a virtual terminal while running X seems to crash the OS. SDL is not actually dependent on X and you can use it without X running. Just remember to set a good video mode or you’ll get 16 colors. Use mplayer -vo sdl filename
• aa: Ascii Art (aalib) is a fun way to look at videos but it gets old quick if you haven’t set the terminal to a high enough resolution. Too low and everything will look like gibberish but with a higher resolution you can make out quite a lot of details. Use mplayer -vo aa filename to get ascii art versions of your video. Really high ‘Cool Factor’ =)
• libcaca: Colour Ascii Art, similar to aa but some text is in colour and the detail is usually better. Haven’t been able to get it going under just a virtual terminal though. Use mplayer -vo caca filename
• vesa: Use the VESA VBE 2.0 output. Haven’t been able to get this to work yet.
• cvidix: Console Vidix. You need to have a working vidix driver. I don’t know how to get one yet.