Should I imagine it like a TCP/UDP port (per-machine rather than per-user)?
It actually is a unix domain socket for local users, and a TCP port (if enabled, on modern X servers it's disabled by default).
Can I connect to an other users DISPLAY?
Yes, with proper authorization. See
Can I list the currently used DISPLAY numbers for one user?
Display numbers are per X server, and not per user.
Is it possible to find one free DISPLAY number that I can still use?
ps axu | grep Xorg should list all X servers, you can see which display number they use. Or look at
/tmp/.X11-unix/ to see the unix domain sockets. Possibly there are variations for this among distros.
In general you should have an idea how many X servers are running on your system, if you have root rights and configured it ...