I have 2 PC's both with Debian wheezy installed.
One of them without any X-window system.
Question is: Is it really possible to get network rendering to work in that situation?
Yes, just get a working slave config on your first computer, save the config on the second comp and use the command line : blender -b slavecfg.blend -a
Read the wiki : http://wiki.blender.org/index.php/Doc:2.6/Manual/Render/Performance/Netrender