What happens at a border when you need an additional stamp, but don't
have empty pages, or even no free space left?
This depends on the entry procedures at the border.
At almost all border posts, your passport has to be stamped; this stamp is later verified at multiple check points. This stamp is your proof of legal entry into the country or territory. This stamp is required even if you hold valid travel authorization to the destination country; hence most ports will deny you entry if your passport is full.
However, certain countries have "e-gate" procedures. This means that you can cross the border without carrying a passport. You instead travel on your country ID, and biometric data is scanned to log your entry. Obviously here you don't need a passport at all, so the free page requirement is also moot.
Even with e-gate enabled ports, it is always recommended to carry your passport and make sure that it has free pages. This is to ensure that should the e-gate be under maintenance, you are still able to cross immigration.
The most popular e-gate enabled border post that I have been to is Dubai International Airport (OMDB); where there are dedicated e-gate lanes that are completely automated (no immigration officer at all).
In addition, GCC (Gulf Cooperation Council) citizens can travel across GCC member states if they have a digital identification card. In this scenario, a passport is not required.
Some countries will offer you a separate "stamp book" if you travel often. This book is to make sure you don't fill up your passport during frequent transits. I have used such a book when residing in Saudi Arabia and studying in Bahrain. You need both the book and the passport. The passport has the visa, but the immigration officer will stamp the book instead.
Some countries offer their citizens passports with extra pages at nominal costs; you can request this at the time of passport renewal.