Ok, this is one of the more serious situations which a traveller can meet. It depends where you are and how big the city is. I describe the situations which you can have with growing despair.
- In big cities it is normally always possible to stay at the airport or the train station (there are always people/information desks which you can ask). There are some situations which can give you some trouble:
- The city has a convention/meeting/event and the hotels are overbooked.
- For whatever reason you are in a city part which is completely empty at night (factories, offices). Such parts can be very intimidating if the area is deserted.
The first places to go are the places which are by default open 24 hours or at night:
- Police station
- Hospitals and ambulances
- Amusement halls
Another option are religious places like church, synagogue, mosque etc which you can ask (do not expect too much friendliness, but at least they are obliged to have a bad conscience if they reject you).
As some commenters pointed out, it is culture dependent if you can expect that police stations or religious places are manned at night. For outbooked city parts the very last option to have a night in a room is normally the red-light district which is conveniently open at night.
Let's say you are in a deserted part of the town. Search for light and noise and head towards it, move silently and are attentive (listening, seeing) while you are on your way. If the street has different lighting (bright, dark, bright) close one of your eyes in the bright part to retain night vision. Women: If you have high heels, break them immediately off, they are way too conspicous and prevent both listening and running. Go against the traffic flow to see immediately if some car is coming and how it reacts to your presence. If he/she stops and offers help, decide if you have a good or bad vibe immediately and either accept or decline.
If you cannot get a room, try to find other people with the same problem (again, let your immediate impression decide) and search together for a place. This will be parks, open places etc. where other people with the same problem occur. If you are at least two, one is awake and watches to avoid being ripped off.
If you are stranded in a small city where everybody knows everybody, it can be that there is no police and ambulance buildings. In this case act diametrically to the description of the deserted part: Prefer walking in the bright light and step quite noisily to announce your presence. Talk to people if you meet them and explain the situation. If nobody is outside, have a look at the buildings. Look out for well-groomed houses with many adjacent neighbors and bright colors, trees and happy figurines (frogs, small children), something like that. If you enter the area, make yourself as noticeable as possible (knock at the garden gate and shout if anyone is home). Simply ask for help and offer that you sleep in the garden/shed whatever. The person will likely either offer you a place to sleep or with almost near certainty know someone who could offer you something for the night.
If you are really at the end of the world (There are in fact airports outside all cities, hello, RyanAir) and you cannot find even a shed, then sleep in the woods (naturally only if there are no bears or worse things). Try to get old newspapers/tinfoil (which are quite effective insulators!) and try to find a sleeping place. Woods have a higher temperature, give you some protection against wind and rain and are dew-free.