To determine whether it's possible to be deported in this situation, it would first be necessary to distinguish between various types of removals, e.g. removal at port when you have been denied entry right out of the plane/at the border, removal for some immigration violation, or deportation after a criminal conviction. Many other details can also matter.
Also, the exact procedure will vary somewhat from one country to the next, as it depends on local law. What you found is a generic warning from the perspective of the receiving country but it does not mean that most countries can or do deport stateless people. I think it's mostly intended to scare people off renouncing their citizenship, especially if they naively think this would be an easy way to avoid being removed from a country where they are staying illegally.
But in any case, removing someone typically involves the country where you want to send them to, especially if the person to be removed has no valid travel document. Even if you are in fact a citizen, if you ditched your passport, the deporting state will contact the relevant consulate to obtain permission to deport you to that country. But the world is a vast place and there have been cases of countries taking some liberties with these principles or of consulates accepting people who had no link with them.
What happens after that will also vary. If you somehow managed to reach the territory of a country and are found to have no right to be there, you can typically be detained. If the country can't find a way to remove you, you could be detained indefinitely or simply released after some time. Being caught at the border or only later also makes a difference in terms of the applicable procedure.
Now, to be a little more specific, I can tell you how it's supposed to work in France (I only chose France because that's the country I am most familiar with). If you land in France and you are refused entry, the carrier that brought you there generally has to bring you back to your point of departure, your country of citizenship or any place that will admit you (but this provision does not apply if you have been removed to France by another country, to avoid “bouncing” people back-and-forth between two countries).
In the meantime, you can in any case be detained for up to four days, during which you can appeal the decision to refuse you entry, lodge an asylum application, ask your consulate or the person you wanted to visit to be informed of your situation or ask to see a lawyer or advisor (there are pro bono legal advisors employed by state-funded charities who work in those detention centres) or a medical doctor. You can also leave at any time if it's to go elsewhere than France. This 4-day delay can be extended several times by a judge, up to 20 days in total, if the authorities can prove they have a good chance to find a place to send you but need the extra delay.
At the end of this period, if they haven't found any solution (and you haven't filed for asylum), you are released with an 8-day visa and officially “invited” to leave the country before the end of this period. Obviously, everybody knows that there is a great chance you will abscond and simply remain in the country illegally but that's the way used to deal with this in a legally plausible manner.
After that, if you are still in France, you are in the same situation as thousands of undocumented migrants (or “sans-papiers”). If you get caught for some reason (random police check, raid on a place where you work illegally, etc.), the authorities can detain you again (for 5 days at first, extendable by a judge, now up to 90 days in total) and get a shot at deporting you. If they still cannot (no consulate will recognise you, you come from a dangerous country, etc.), you will be released again. In practice, the authorities (police, etc.) try to avoid wasting resources on people they will ultimately have to release so if they know you cannot be forcibly removed (because of your personal situation, because your country is at war, etc.), they will often simply let you go.
The actual conditions are pretty harsh (and deteriorating) but legally, this detention is not a punishment and should only happen to the extent that it facilitates your removal. That's why people should in principle be released as soon as it becomes clear that timely removal will be impossible. I have heard before of people being released en masse following a coup in their country of origin, as judges would deem the situation too unstable to expect a removal in the next 90 days.
Depending on your personal situation, you might eventually find a way to qualify for some sort of residence permit (but having stayed illegally in the past basically disqualifies you for naturalisation, even decades down the line). Obviously you cannot work legally and if you are also stateless and have no ID, many other things are extremely complicated.
Most of this should be pretty typical, at least for European countries, even if there are occasionally a few surprising differences. How long (or even whether) you can be detained varies a lot for example, all the way to indefinite or prison detention in some places.