Heres a few folk that have done big journeys on horseback one did it for the bbc[swopped to camel] halfway through.
Tim Cope- hungary to mongolia.
Andreas Hutter- hes been around a bit sites in german I think.
Benedict Allen-bbc report on his journey, he has also written a few books.
Im sure theres been a few folk done S.America, and as people have walked AFrica if wouldnt surprise me if that hasnt been done either. N.America and australia should also be possible.
Hotter countries you would probably need an arab or a local species, colder maybe fjord pony or highland/connamara type horse, all have a great rep for long distance riding among the endurance riders. Would more likley be a pony you would end up on as very few horses can hack that can of daily grind in the long run or are as sure footed for the rough stuff. Our clydesdale x and shire x did well on long distance but that was 1 or 2 day events but they had feet like dinner plates and went through alot of shoes.
On a more local note when I worked on the estates of royal deeside in scotland with horses we did 3 day hacks as well as the odd 7 day ones from glenntannar aboyne all over the place. The old guy that lived next door was one of the last living cattle drovers and he used to walk cattle from the highlands right down to the borders, these roads are still mostly non tarmac ones through great scenery.
You could however take long rides in just about any country theres plenty of places offering long distance touring on horseback all over the world, and like bikers theres horse nuts everywhere as well as locals still using them, the biggest issue would be transmitting equine diseases.