How would an American returning from international travel prove his citizenship before 1914?

Short answer

While it is true that there was no specific legal requirement for Americans entering the US to have a passport prior to WWI, passengers were not unused to being required to present some kind of documentation even before 1900. In fact, the documents which they were likely to need when visiting many areas overseas would also get them back into the US.

The widespread adoption of passports after WWI did not mean that some kind of documentation was not carried by travellers in the early 1900s and before. What was lacking was standardization of documents and - in all probability - the way officials applied what laws there were.

Among the documents - aside from early (photo-less) passports - that could be used were birth certificates, certificates of naturalization, military records and (for women) marriage certificates. Entering the US by land from Canada or Mexico would have been easy without documents as vast stretches of these borders had no controls.

---

Details

Getting into the US in the early 1900s was not difficult for either Americans or foreigners unless you were Chinese (or, from 1907, Japanese) or (from 1903) fell into one of the categories of "anarchists, people with epilepsy, beggars, and importers of prostitutes.". Otherwise,

immigration into United States was numerically unrestricted, reflecting a tradition of laissez-faire labor mobility that dated to the colonial period. Freedom of movement was a right acquired in Europe and North America with the emergence of capitalism, as peasants became unshackled from their places of birth and servants from the authority of their masters....State control of migration was considered either a matter of local police powers (vagrancy, dependency, etc.) or a matter of commerce.

Source: Mae M. Ngai, Impossible Subjects: Illegal Aliens and the making of Modern America

Also,

In 1868, American citizenship was automatically granted to all African Americans born in the United States or naturalized. No applications were required.

Source: Kathryn Miller Marshall, 'The Path from Passenger Lists to Naturalization Records'

By the early 1900s, the requirement that all ships provide a passenger list / manifest was being strictly enforced. These lists required passengers to provide (among other things) nationality, age, occupation and final destination in the US. An important point here is that

U.S. customs officials or Immigration Services did not create ship passenger lists. Ship manifests were completed, generally at the point of departure, by steamship companies. These passenger manifests were then submitted to the immigration officials upon arrival in the United States.

Most of the required information on passenger lists was usually filled in by ships' officials, not by US immigration. This happened both prior to departure and on board; passenger lists with crossed out names of individuals who did not actually board show that the information was already fairly complete before departure. Thus, documentary evidence - if requested - had to be provided already at the port of departure.

Passports did not suddenly appear in 1920. Even in the immediate aftermath of American independence, there was a recognized need for Americans to have some kind of documentation when travelling abroad:

The first US Legation was established in 1777 and by 1780 some of the US passports issued in Paris and London already bore descriptions of their holders and a stated duration of validity, usually three or six months.

Source: Martin Lloyd, The Passport: The History of Man's Most Travelled Document

Further,

Although the Department of Foreign Affairs was the countrywide authority to issue American passports this did not stop the Governors of the individual American states from still issuing their own passports and so travellers could now choose to equip themselves with a passport issued for foreign travel by the state or city in which they were resident or one of the new 'Departmental Passports' as they were called.

Source: Lloyd

Passport issued to one John L. Livingston in 1889 which identifies him as a Citizen of the United States. There's a physical description down the left side. Image source: antipodean.com

Although passports were not that common, few Americans needed them as few travelled abroad. Even so, over 250,000 passports were issued and renewed by the US Secretary of State between 1898 and 1913. From the 1850s onwards, Americans had became increasingly aware of the possible need to provide proof of citizenship, or at least US residence:

Between the 1850s and 1930s.... Newspapers filled pages with stories on the “passport nuisance” — the term used to cover the perceived absurdity that the government would force people of the “better” class to be documented like common criminals. Ladies blushed at having to tell their age to a clerk. Gentlemen objected to having their romantic notions of individual character reduced to a generic list of physical traits. Headlines like “W.K. Vanderbilt Tries to Identify Himself” detailed bureaucratic bothers, and the fact that President Woodrow Wilson needed a passport made front-page news.

"One of the earliest passport photos, from 1914, appears to have been added later as requirements were updated." Text & image source: Atlas Obscura

For those who didn't have a passport, other documents could be used. Annotations on passenger lists are evidence of this:

USB or USC - Indicates "U.S. born" or "U.S. citizen" and is sometimes found noted on the manifests for U.S. citizens returning from a trip abroad.

"The "USB" annotation is often seen in the case of children returning home after a visit abroad with their foreign-born parents." Text & image source

"The annotated "USC" appears in the nationality column. Farther right, in empty space, is the reference to his naturalization in the Superior Court at Cedar Rapids, Iowa, on October 31, 1911." Text & image source

Examples of documents provided include:

C followed by a bunch of numbers - usually stamped or handwritten near the individual's name on the passenger manifest. This refers to the Naturalization certificate number.

and

432731/435765 - Numbers in this format generally refer to a permanent U.S. resident returning from a visit abroad with a Reentry Permit.

Certificate of Citizenship , 1888. Image source: militaryantiquesmuseum.com

As women automatically gained citizenship when marrying an American, marriage certificates could also be used (assuming the husband could prove his status), while birth certificates could prove that a child was USB (US born). Also, for US citizens who were foreign-born,

Censuses, military records, court minutes, homestead records, passports, and voting registers may provide evidence that an immigrant obtained citizenship.

Source: Marshall

Prior to 1906, there was little standardization as individual states issued a range of documents which could be used by an American as proof of citizenship. Even certificates of naturalization

were of all sorts, sizes, shapes, and colors, and kept in all sorts of ways, depending on the personal ideas of each of the several thousand clerks of courts exercising naturalization jurisdiction

Following the Naturalization Act of 1906, this changed. Among other things, the law now required that all naturalization courts nationwide

Issue a Certificate of Naturalization to every naturalized person (and name all members of the primary subject’s family who derived citizenship from his or her naturalization);[xv]

This was enough for entry into the US, but it was not necessarily enough for travel in Europe. For example,

Germany declared war on Russia on 1 August 1914 and immediately the US Embassy in Berlin was besieged by hundreds of American citizens demanding the passports that they had not needed until then....

...In order to leave Germany, all Americans had to submit their passports to the German Foreign Ministry...

Source: Lloyd

Early passports, though, could be "purloined", as was the case with the German spy Carl Hans Lody who was had an American passport (under the name Charles A. Inglis) and an American accent, but was caught by the British and executed in 1914.

---

Let us also consider that, in the eyes of some officials at least, having status and wealth lessened the burden of proof. Any passenger of some means would almost certainly travel 1st or 2nd class. This in itself could be important to avoid being mistakenly / wrongly sent to (for example) Ellis Island. Note that

First and second class passengers were all inspected on-board, and only went to Ellis Island if they were detained or held for Special Inquiry.

whereas

Immigrant steerage passengers were offloaded directly from some liners onto a barge or ferry and taken to Ellis Island. The first "land" they touched would have been Ellis Island. Other steerage passengers disembarked from the liner at the steamship company docks then boarded a ferry to Ellis Island.

If a passenger could not provide documentary evidence as requested upon arrival, there was still one option: an American (and even a non-American) could provide names of local people for immigration to contact to verify residence, employment etc.

---

By land, an American without any kind of documentation would simply have had to avoid the few inspection points. From 1894, some routes from Canada into the US were controlled but anyone seeking entry (American or otherwise) would have had plenty of other options. Likewise the Mexico - US border where, until 1915, no more than 75

Mounted watchmen of the U.S. Immigration Service patrolled the border in an effort to prevent illegal crossings as early as 1904, but their efforts were irregular and undertaken only when resources permitted....