It depends on whether or not you have internet access.
If you do, then you have the wealth of information on the internet to help you: As you asked "what to do if you arrive at your destination after a long journey only to learn that your intended accommodation, is either overbooked or non-existent." that means you will have probably less than 12 hours before needing a place to sleep. As many internet booking sites require 24 hours notice, they are probably not suitable to use directly. However, you can use these sites to find suitable hotels with good ratings near your current location, and then go to those hotels directly and see if they have rooms. www.agoda.com, www.expedia.com, www.booking.com are all options that I have used before with plenty of success. As the name suggests, www.lastminute.com does allow bookings on the check-in day, so that is also a good option.
If you don't have internet access then your best bet is to try to find a taxi driver who speaks your language and ask him to bring to an area with a lot of hotels. That's a better option than just asking him to bring you to a hotel, as at least this way you will have several options nearby in case the first is full or unsuitable.
All that said, as you have time in advance to prepare I would just take down the numbers and addresses of a few suitable 'backup' hotels in case you run into trouble with the one that you have booked.