Shower is one of the challenges of the traveller and finding good shower spots is nice survival skill to develop. While hitchhiking for example, try to stay fresh while traveling as it is a form of respect to the people that take you in their car or in their home.
With only a small sink, you can already give a quick wash to your face, hands, armpits, maybe feet and personal area. Then the luxury option is to change t-shirt and underwear.
Depending on the countries of course, options are really different. And while washing in public spaces or in "half-hidden" spaces, keep in mind that people might be shocked if you are washing yourself nacked. Showering in a place where there is a chance that locals pass by, make sure you know enough the culture to decide whether you take off your leopard panty or not.
If you know that you are likely to wash yourself in natural places, try to have a 100% natural origin soap/shampoo, or the most biodegradable you can find.
- Classic: of course, rivers and waterfalls are pretty awesome! As long as the water is quite clean and that some of your wounds don't infect because of this.
- Sea lovers: the first option is to go directly showering in the sea. Sensitive skins can react to long term sea washing or staying several days with salt on you.
Be careful in the case of a river or the sea: you are under a 30°-sun, beautiful blue water, but nobody swimming, then first ask yourself why, then ask the locals. In some rare seas, jellyfishes can go from nasty to deadly, and in some rivers salt water crocodiles might want you to share a bit of your leg with them (Australia is a pretty good example for these kind of stuff). Sometimes the water is just too polluted even if it doesn't look like it. But most of the time you should be just fine ;)
The second option are the beach showers, in open-air or in a building, often available next to city beaches or well frequented ones. This of course depends a lot of the country.
- Student nostalgie: in some well-equiped universities and campuses, toilets have showers. It can be worth having a look if you are not far from it.
- Do it like a truckie: truck drivers, like normal people, shower as well from time to time. So often in petrol stations or special truck stops, showers are available. They might not be free though, but ask the cashdesk and explain your situation with your greatest smile.
- Football is my favourite sport: Football fields are to find in many cities, so just go in if the showers are open or ask around and people will be likely to help you.
- Spontaneous shower: especially if you speak the language, you can explain to people your travelling situation and ask people for a shower. Hotels/hostels/motels just after the check-out time of the customers can be a good option as well, as the hotel didn't clean the rooms yet. You can always tell them first that you are willing to give away a coin for it and there is a good chance they don't even take it.
- Pirate life: if you are on the coast in a popular sailing destination, the marina will be equipped with showers. Usually the door can only be open with a card, but if you just wait for someone to come in, you should be able to get in without problems.