Is it possible to run Selenium scripts without having an X server running, too?
Yes, you need to have X server running because Selenium requires a running browser and browsers need some kind of X server in order to run.
Fortunately there are many types of X servers and one of them is Xvfb aka X virtual framebuffer that does all the operations in memory and thus requires no screen.
Wikipedia has also some nice examples.
Also there are lots of questions here on SO for keywords headless, xvfb and selenium. Choose wisely ;)
[Edit]: Here's a nice example.