Countries provide travel documents for citizens of other countries, or stateless persons. These documents are called "Laissez Passer" (French for "Let through").
Usually, Laissez-Passer holders are required for visas to any country.
Prominent examples:
Jews from many countries were forced to renounce local citizenships when they wanted to immigrate to Israel. Some of those countries (like Iraq in the Wikipedia example, or more recently - Soviet Union) provided Laissez-passer's to these Jews, valid for travel to Israel.
Israeli Arabs traveling to Saudi Arabia were (and may be still are) using Jordanian travel documents, because they cannot use their Israeli passports in the Saudi Arabia.
People working for international organizations (UN, Red Cross, etc) have travel documents issued by these organizations. Some refugees (stateless persons) have travel documents issued by international organizations as well.
