Tricky, particularly the POD. Remember the French Foreign Legion's origins come from the Post-Napoleonic Period. The young male population had been obliterated and as France expanded into North Africa in the 1820s and hoped to return to its position as one of the key European powers it needed boots on the ground. As such the Legion was basically France paying foriegners to fight for them, and the units reputation saw it continue long after it was nessecary.
I don't believe Empire building, direct or otherwise is key to a US Foreign Legion. Rather the need for troops being met by recruitment overseas. Here the USA has obvious mass influx of immigrants making such needs nonexistant for most of its history.
The only time a true USFL would be formed IMO would be during the nation's first 50 years or so when the threat of Brits, Indians, Mexicans and even Barbary pirates all might overstretch the Republic's small population base. Say a more bloody War of 1812? A prolonged US presence in North Africa? Maybe even direct American involvement in the Napoleonic Wars? All offer possible situations were the Yanks will truly require foreign soldiers to help.
This doesn't follow the OP guidelines but really a vast population and a history of heavy immigration make specialised foreign units in the Legion's mold seem pretty impossible post-1945.
The only thing I can think of is a Gurkha style force as suggested by the Baron. Filippino scouts is an option, another that leaps to mind is the Hmong of Vietnam. Say the Americans take a more indirect involvement in 'Nam, focusing on inbedding elite units in local forces and the fortified village strategy aiming for hearts and minds over body count. the War goes better for the South, plus say the State Department takes advantage of the Sino-Soviet split alot earlier and gets Chinese help cutting off Soviet aid to the North.
Regardless, the War is won or at least a Korean style stalemate is sorted out. The Hmong, instead of being mass evacuated to America, are granted a Gurkha style deal due to their fanatical anti-communism and martial prowess. Their economic conditions makes such enlsitment an obvious 'easy' way of bringing real wealth back to the Hmong villages. So after a successful though bloody war the United States has a solid stock of loyal, elite troops more tolerant of combat losses and detached from the problems of conscription and dropping enlistment numbers in an increasingy dovish USA.
As such Hmong battalions see action around the world, often acting as the first wave in any conventional military action, with paritcular attention to deployments in hilly and tropical combat zones.