Most pre-modern theories on Native American origins fall into three general categories: migration of a single group from the Old World, migrations of multiple groups, or an autochthonous people.
You might be surprised, however, at how far back the idea of a landbridge between Asia and the America goes -- Alexander von Humboldt's (1810) Vues de cordilleres et monuments was proposing that the Americas were peopled from Asia by way of the Bering Strait. Even as early as 1589, the Jesuit Fray Jose Acosta was proposing an Asian origin for Native Americans, by way of a land journey. His basis was biblical, based on the tenet that all of mankind was descended from Adam and therefore the inhabitants of the Americas must have come from the "Old World." Since the animals must have come from there as well, and transporting the very large animals would have been difficult, his reasoning went that the voyage must have been by land.
Acosta's Asian route had the advantage of that particular area of the world being largely un-mapped by Europeans at the time. This also allowed him to comment on two other consistent themes in explaining the origins of Americans: an Atlantic crossing and possibility of being lost Israelites.
The former he dismissed as without evidence, and took time to specifically ridicule the proposal that Americans had fled from Atlantis, which he saw as clearly a myth. He likewise saw no evidence for a Hebraic origin of Americans, noting that Jewish identity was so strong and continuous that the lack of clearly Jewish customs among Americans argued against that proposition.
Others, such as Fray Diego Duran, were less inclined to discount the idea of Jewish Native Americans. In the first chapter of his 1581 history of the Aztecs, he accepts as self-evident that Americans were descendants from the 10 Tribes lost to Shalmaneser. He draws comparisons between Aztec and Biblical stories to form his argument, even arguing that the Spanish Conquest was a fulfillment of scripture.
The idea of "Israelite-Americans" even gained acceptance among European Jews, with Rabbi Manasseh ben Israel's Hope of Israel (1650) specifically taking up the cause. James Adair's (1775) The History of the American Indians was probably the most vociferous proponent of this idea, putting forth 23 arguments based on similarities he found in language, idioms, funeral rituals, religious beliefs, style of dress, and marriage customs, among others. That Americans look nothing like Hebrews bothers him not at all, as he correctly notes the mutability of skin tone, even if his assertion that "[w]e have good authority of a Spanish lady, who conceived, and was delivered of a negro child, by means of a black picture that hung on the wall, opposite to the bed where she lay," is... dubious. Amusingly, he rejects a Chinese origin on the grounds of the distance being too far to travel (assuming an ocean voyage).
Other single-origin theories abounded, some of which relied on some incredibly rapid settlement and diffusion across the continents. Hakluyt's (1589) The Principal Navigations, Voyages, Traffiques and Discoveries of the English Nation posited that the mythical Welsh Prince Madoc sailed to the Americas in the 12th C. and, finding them uninhabited, returned with settlers. Oviedo's was writing in 1535 that the Americas could have been peopled by Iberians fleeing from the 8th C. Muslim advance. Far more common, however, were Egyptian, Phoenician, Greek, Scythian, or "Tartar" (i.e., Mongol) settlers. Bancroft's (1874) The Native Races put it thusly:
The American Indians, their origin and consanguinity, have, from the days of Columbus to the present time proved no less a knotty question. Schoolmen and scientists count their theories by hundreds, each sustaining some pet conjecture, with a logical clearness equaled only by the facility with which he demolishes all the rest. One proves their origin by holy writ; another by the writings of ancient philosophers; another by the sage sayings of the Fathers. One discovers in them Phœnician merchants; another, the ten lost tribes of Israel. They are tracked with equal certainty from Scandinavia, from Ireland, from Iceland, from Greenland, across Bering Strait, across the northern Pacific, the southern Pacific, from the Polynesian Islands, from Australia, from Africa. Venturesome Carthaginians were thrown upon the eastern shore; Japanese junks on the western. The breezes that wafted hither America's primogenitors are still blowing, and the ocean currents by which they came cease not yet to flow. The finely spun webs of logic by which these fancies are maintained would prove amusing, did not the profound earnestness of their respective advocates render them ridiculous.
These various ideas of how the Americas were peopled were not mutually exclusive. Gregorio Garcia hypothesized in 1607 that, after Noah's Flood, there had been multiple crossings into the Americas by various peoples, a view that Torquemada's (1615) Monarchia indiana shared. My personal favorite theory is what Samual L. Mitchell was teaching at Columbia in the early 19th C., that there were 3 original groups of immigrants -- Malays, Tartars, and Scandinavians -- but that the Tartars waged a genocidal war on the other two, finally wiping out the last traces of them in what is today upstate New York. LDS founder Joseph Smith was apparently a fan of Mitchell, and early on sent him copies of the characters from him purported gold plates, asking for his linguistic opinion (Mitchell declined). As late as 1935, the famed anthropologist Ales Hrdlicka saw fit to discuss the possibility of Asiatic migrants coming over via the Bering Strait and Melanesian migrants arriving by way of Australia and Polynesia, if only to throw shade on that latter hypothesis.
The focus on Old World peoples coming to the Americas was based on biblical monogenism, the idea that all people everywhere were descendants of Adam. There were, however, always some pre-Adamite ideas or theories of separate creations. Isaac le Preyrere in the mid to late 17th C. was a general proponent of there being humans on the Earth prior to Adam, a view which he applied to American origins. Adair specifically calls out Lord Kames' (1734) Sketches on the History of Man for proposing that there had been 3 separate creations: White, Black, and Yellow. These beliefs would eventually give rise to the idea of a polygenic origin of humanity, the early scientific hypothesis that mankind had evolved separately in various locations. Samuel Morton, in the 19th C. was a famous proponent of independent evolutions, which he used to explain racial differences. Beider's (1986) Science Encounters the Indian, 1820-1880: The Early Years of American Ethnology is a great resource if you want to read up on this strain of thought, among other topics involving armchair anthropology and scientific racism.
Speaking of scientific racism, one common problem that monogenist theories positing that Americans were originally Phoenicians or Scandinavians had to deal with was their differing appearances. The belief that climate could produce that various physical permutations of humanity was a widely held belief, and was a key point to Blumenbach's late 18th C. categorization of humanity in to 5 different races, of which the Americans were one group. This has some merit, since latitude and climate can have influences on melanin and craniofacial morphology. Since this was colonial era European "science" however, the focus was on showing how all non-Whites were somehow "degenerate." The relative uniformity of the Americas, however, presented a problem.
The Comte de Buffon, who never visited the Americas, explained away the lack of variation by theorizing that not only were Americans recent arrivals to the continents, but that the landmasses themselves had only recently risen from the waters. This, to him, also explained why American animals were quite small in comparison to Afro-Eurasian species, a notion Thomas Jefferson dispelled by sending him the body of a moose. My personal favorite explanation, however, comes from Cornelius de Pauw, who similarly never went left Europe. While he shared Buffon's notion that the Americas were an intrinsically cold and damp place, which led to physical and mental decline, he thought Native Americans had long dwelled there, following the Flood. As evidence of this, he cited their incredible degeneracy, wherein most of the men were passion-less homosexuals whose penises needed to be swelled with insect bites in order to mate with the women, whose excessively lubricated genitals allowed children to slip out effortless.
So there you have it. Prior to the LGM Bering Land-bridge gaining ubiquitous acceptance, Americans were thought of as a mish-mash Old World peoples, or maybe just Jews, or maybe they were there the whole time. Maybe they were just inferior to begin with, or maybe they had lost or perverted the "civilization" of the Old World. There were as many theories as people to make them.