My (infrequent) leisure travel is mainly in non-safari, non-tourist Africa. Since there are no hotels, nor proper "stores" - not to mention no restaurants - travel can be relative cheap. Bicycles are inexpensive for short-distance travel and taxi brousse for longer distances. It's not for everyone, but it's the only way to see Africa.

Airfares can be expensive, particularly since there aren't many low cost carriers providing international/intercontinental coverage.

Malaysia is very cheap if you want high quality.

If you want really cheap look into India/Nepal - though quality comes at a high price.

Armenia.

India and Nepal are inexpensive for what you get, but the need to (usually) hire drivers and guides probably moves them out of the cheapest of the cheap destinations. You generally can't self-drive rental cars in either location, and most visitors wouldn't want to if they could.

We did a non-technical trek when we were in Nepal...we had a great time and met a lot of interesting people along the way and felt like it was great value, even though we were sleeping in the most bare-bones teahouse bunks imaginable. I've been told that higher-altitude and more technical treks get a lot more expensive.

We did a Golden Triangle tour in India. I first approached it thinking we could do it without a guide...use trains and internal flights between the cities. But the timing and hassle factor of all of that led us right back to hiring a private driver, which worked out fine.

We also did 11 days in Egypt rather inexpensively in 2009, thanks to Hilton and Marriott awards in Luxor and Cairo. The only modestly expensive part was a daytrip out to Abu Simbel, which is a short flight from Aswan. We hired a driver to take us around Aswan and then back up to Luxor, stopping at a camel market and a couple temples along the way. Very much worth it...

Thailand..Hotels at all levels are inexpensive by US standards and great food can be had on the street

Cheapest places I've been to are probably Cambodia (I bought a horrendous bottle of vodka for about $1), India (some great value hotel rooms) and Vietnam (as someone else mentioned very cheap, but awful, beer)

No place is going to be as cheap as you remember from the last time as you need to pay double to triple the price for accommodations. Based on your budget select the place start enjoying your vacations. Some suggestible locations are: Costa Rica, Albania, Turkey, Greece, Philippines

That doesn't sound cheap at all when compared with Laos, Iran or Sri Lanka where good meals can be had for $3-4.

Costa Rica is not that cheap compared to other countries in Central America. However, Albania is great for food and accommodation. There's lots of meat and produce available locally and serving sizes are generous. I had trouble finishing meals on my trip there in 2013.

In Sri Lanka last summer I found food and accommodations not so cheap unless you get off the tourist path. Lots of resort hotels on the coast charge a lot for meals (like resorts in other countries) because there is nothing else around. To get off the resort into town even costs a lot for the tuk tuk rides.

I would imagine Russia isn't so bad about now- if you're paying in Rubles.

+1

There are even cheaper regions of the world to visit. But I'd say that SE Asia is the best value region in terms of the combination of quality of service, accommodations hygiene, and, in many parts of the region, infrastructure. Much cheaper than the Caribbean, Central and Eastern Europe and much of Latin America, for instance. I'm sure that parts of South Asia and Africa are cheaper than SE Asia; but no matter what your price point is, it will cost less for a given quality hotel or meal in much of SE Asia in comparison with the rest of the world.

+1 again.

And I'd say that Thailand is the best value of all. There are less expensive countries in SE Asia (and again, in other regions). But the combination of good quality at a relatively low price in Thailand is the best. That's why it's one of the few countries my wife and I repeatedly go back to on our vacations.

Right now - Russia...

Vietnam in South East Asia. I suppose Vietnam is worthy for you to enjoy sightseeing and relaxing as well. This country has both moutainous and coastal areas. It is not only cheap but also very safe and friendly, a good choice for your plan. Good luck!

Obviously not as cheap as other places mentioned here but cheap for Europe in case OP feels like going to Europe.

I just booked a hotel in Moscow for a stay in September. I paid about half of what I paid for a stay in the summer of 2013 (same hotel).
I am strongly considering buying Rubles already now for the trip.