I have heard that British Airways provides free stopover in London i.e. a flight by British Airways via London costs the same as two separate flights from departure city to London and from London to destination city. So does Airfrance with Paris. Also I have recently seen an ad in subway about free stopover in Iceland from Icaelandair. Do you know more elsewhere, especially in Asia?
Most airlines don't charge extra for stopovers (in fact, more often, they charge less, because the route is less convenient than a non-stop flight). They like to advertise "free stopovers" to make you think this is a great benefit they are giving you.
For example, if you are flying from New York to Dubai, the rich business traveller is going to want to take Emirates nonstop. Since Emirates is the only airline operating that route nonstop, they can charge whatever they want (it's showing as $2270 right now). Meanwhile, British Airlines, Qatar, Air France, KLM, United, Delta, and Royal Jordanian would all love to take your money on that route, but they can't do it nonstop, so they offer cheaper fares (now showing $1186-$1782) with connections in their home airports (London, Doha, Paris, Amsterdam, Washington, Atlanta, and Amman, respectively). And they will all be happy to let you stay over in their home town for a day or six without extra charge if it induces you to tolerate the connection.
Since very few people actually WANT to go to Iceland, and connecting in Reykjavik is hardly anybody's idea of a good time, Icelandair has to advertise "Free Stopovers" to induce people to think this is a great bargain and a fun thing to do.
IN FACT, in many cases, you will find cheaper fares from A->B->C->B->A than you will find from A->B->A, because of the premium placed on nonstop travel.
To find "free stopovers", just do an online search for your end point, and look at the various connection cities that are available. (Hipmunk does a good job of this). Then if you want to book it, redo the search as a multilegged trip and you should see that the calculated fare is the same or even cheaper depending on travel days.
So for example, if you want to see what stopovers are available from New York to Dubai, you do the search in Hipmunk and you'll see various flights connecting in London, Doha, Paris, Amsterdam, Washington, Atlanta, and Amman. So now you can search for multi-legged journeys from New York to Paris to Dubai to New York and the fare should come out similar to the Paris connection option. (I actually just tried that and saw that it was about $30 more, which is probably just an airport tax).
The best stopover options are in major cities where large airlines have their hubs. So even though Lufthansa isn't advertising anything on the New York to Dubai route, I'm pretty sure that I could search for New York - Frankfurt - Dubai - New York and find a fare that was pretty cheap compared to the New York - Dubai nonstop. (I just tried that and it was $800 less to stop in Frankfurt than to go nonstop, and only $100 more than the cheapest connection).
If you are planning to stopover anyway, that may create an opportunity to travel on Tuesday or Wednesday when fares are lowest.
Agree with Joel for the most part - playing with kayak or hipmunk will reveal all sorts of crazy routes and deals. Two days ago I was seriously considering getting from Mongolia to London by taking a flight to China, or even via Dubai, as flying with multiple airlines on strange routes was working out cheaper, and I enjoy flying :)
However, the next day a new one popped up - it was cheaper to fly to Moscow with airline A, wait 6 hours, and switch to Airline B for the flight to London.
And then yesterday when I came to book, Aeroflot had dropped their prices so it was cheaper to just go Mongolia to Moscow to London with them alone.
I wanted to go to Egypt from London at short notice a few years ago, and found using FOUR airlines to get there and back, it worked out cheap:
LON -> Brussels (had a few hours and an overnight there to check out the city)
Brussels -> Cairo (arrived a couple of days before my tour, so checked out Alexandria as well)
Cairo -> Cologne (amazing cathedral, have been back twice since)
Cologne -> London
Meaning I got to see two extra cities AND save myself a LOT of money than I would have by just searching LON -> CAIRO.