europe, asia, australia and new zeeland primarily use GSM on 900MHz and 1800MHz.
some north american networks use PCS 1900MHz (sometimes called GSM 1900).
many phones sold in europe can use all three frequency bands. (tripple band
phones, ask any salesman in europe or look at the specification for the phone).

GSM works in a range up to some 25km, so you will not find GSM in unpopulated
places, then you will need to look for something else. a few european counties
still use the analog NMT in parallel with GSM (probably sweden, norway, iceland,
finland) but the GSM-coverage in europe is almost alwas better then NMT, even in
remote areas.
from experiance of hiking in sweden and norway, you might end up without
coverage for a day or two, but rearly for longer then that. all major roads and
aras close to such roads have coverage.

in south america i think they use IDEN, but i know nothing about it.

anyway, what you are looking for is a company near you that uses PCS 1900 plus a
phone that is a so called tripple band phone (at least nokia and ericsson has
such phones).
check with your the phone company that provides PCS 1900, they should know if
their their subscribers can use their phones in europe/austraila/new z.

AT&T and T-mobile i think could be two companies that you can ask, iirc they
have GSM 1900.