I'm willing to send skype messages (each to a single user) from a linux server without GUI using PHP or node.js. It seems like a lot of information online is out of date since SkypeKit is no longer working for Skype and projects like this are broken.
According to the docs here Skype URIs are now the preferred way to send chat messages programmatically, but that same page states a copy of Skype must be running on the same server. However I don't have X server installed so I can't install normal Skype client.
So is it possible to send messages without Skype, or is it possible to install Skype and use on a server with command line only, or I must run another dedicated server with GUI to do this?
You want to send messages from your backend. Your linked reference (and proposed URI solution) is for frontends. This does not fit.
Meanwhile there does not seem to exist a server API for Skype.
I cannot think of any fancy solution to your problem. You could try to set up a Jabber server (which provides an API) with a Skype bridge, but I am not sure if this try will succeed. Skype was always buttoned up concerning their protocol and usage by other clients. I doubt this has gotten any better since the acquisition by Microsoft. This acquisition might have also lead to changes in the protocol, which will run all previous bridge solutions useless. (Maybe instead an MSN bridge works...)
To sum it up: I hardly believe you will be able to create any solution at all, and if there even exists one, the necessary work will likely outrun the result you want to achieve.