Gordon M. Sayre's article A Native American Scoops Lewis and Clark offers a popular presentation and analysis of the story of Moncacht-apé, a Yazoo Indian who may have crossed the continent a century before Lewis and Clark. Moncacht-apé's adventures were recorded for posterity in Le Page du Pratz's Histoire de la Louisiane (first published in 1758, though the link is to a later translation at Project Gutenberg). Du Pratz was a French colonial official in Louisiana from 1718 to 1734, and it was in Natchez, Mississippi that he met the elderly Moncacht-apé. Du Pratz often interviewed natives for his history and for the important map or North America which accompanied the volumes.
Moncacht-apé said that in his youth he had taken two great journeys. The first was to Niagara Falls and then the Atlantic Ocean. The second journey was up the Missouri, across the mountains, and to the Pacific.
Did it really happen? I will let you read Sayre's excellent analysis of the tale. (And don't miss his own translations of Du Pratz and additional commentary at his own website.) But I do want to suggest that if Moncacht-apé did not make the journeys, other Indians surely did. A man can walk across the North American continent in one long season. (Your own sturdy blogger once walked the Appalachian Trail from Georgia to Maine, 2100 miles in five months, a typical time for that journey.) If the person were a respected healer, a native diplomat, or simply sufficiently quick-witted, they could travel along native trade routes easily enough. The narrative of Cabeza de Vaca, who traveled across northern Mexico while serving as a shaman to the natives, suggests what was possible.
The essay by the way is from Common-Place, a wonderful internet journal of early American history.