Has anyone, on arrival and while approaching the immigration line, only to discover that passport is missing/lost. What do you do? How do you prove your nationality
(home or abroad)?

I've wandered over to Tijuana from San Diego having completely forgot my wallet and/or ANY ID whatsoever. Returning, US immigration took it pretty well and simply played me a game of 40 questions for re-admittance to the US. For the most part they can apply common sense and determine if you belong there or not by simply talking to you for a few minutes. Of course there is exactly almost zero percent chance an airline will let you check-in an international flight without a passport so unless you got drunk and lost it in the lounge at the departure airport, it is pretty unlikely you would show up without a passport.

I've never had it happen, but it makes me sick to think about it. Since you can't really get on the airplane without a passport (usually anyway), you'd have to think it was lost on the plane itself. The closest I came was arriving in Nairobi, Kenya years ago with no visa, after specifically being told on the telephone by a Kenyan Consulate officer weeks before that I did not need one. They stuck me over in the "troublemaker" lane to fill out all the necessary paperwork...two hours later I finally got my visa. If a person truly arrived without even a passport, I can only guess they'd be refused entry. If they're feeling charitable, they might let you call your embassy to see if something can be worked out, but failing that, they'd probably just tell you to buy the next ticket back to where you came from.

This isn't actually 100% true.

If an airline can satisfy itself as to your identity, and that you will not be turned away by immigration at your destination, then they will sometimes let you on the plane without your passport after doing some checks with the destination immigration.

This is most likely to occur when someone is flying back to their own country after losing their passport abroad, as immigation can't automatically refuse you entry simply because you don't have your passport.

Its much less likely to occur on an outbound flight though, as most foreign countries would not accept a non national without a passport.

After clearing the immigration, there are many places that you may wonder
around before getting on the plane (shops, restroom, lounge etc)...
chances is you get "caught' before boarding the plane otherwise the only
place it will get lost is in the plane.

On most international flights they usually check your passport again at the gate before letting you on the plane though!

The (now ex)US president of our Japanese-owned company had this happen once. She lost her passport somewhere between JFK and NRT immigration. Search of the plane came up with nothing...do not pass go, do not collect $200, back to JFK on the next flight out.

I've heard of asylum seekers on flights departing from China to Canada shredding their passports and flushing them. Presumably this gives them some sort of advantage to do this.

This happens quite a lot with Asylum seekers from many places.

I believe some do this because if the authorities cannot prove which country the ayslum seeker is originally from, they cannot send them back.

Also some countries are deemed automatically safe by the immigration authorities so you can't apply for asylum from them, so some bogus asylum seekers destroy their passports so they can claim to be from a much more dangerous country.

This happened to me in 2003. Sunday Morning (local) in MUC about an hour before my flight an LH agent started making phone calls to washington. Somehow in the middle of saturday night, he got permission. he personally escorted me through security and got my 29" rollerboard gate checked about 5 minutes before closing the door. Going through US Immigration took a whole 2 minutes using my drivers license since I knew I had to go to the special line.

I never go the LH agents name but to this day I owe the guy an ENORMOUS thank you. I feel bad for not writing ASAP. If anyone knows his name, he had shoulder length brown curley hair. I'm guessing around 5' 11" (180cm). He was the ONLY LH agent who wasn't mean and the guy was phenomenal.

I only know the procedure when already through immigration:

Get in contact with nearest local consulate / embassy of the respective country and report the passport as missing.

They will issue you a certificate about this and it will be sufficient for the airline to check you in. It can also be used as 2nd piece of ID at your home countries immigration.

Some/most places require to show up in person !

Before immigration I would say bad luck. Without a valid passport you have the joy of taking the next flight home except it is your home country where you arrive at.

I've never seen this tested, so who knows how much it actually helps...but I've always heard that it's wise to keep a photocopy of your passport/other docs in your luggage. Obviously smartest to keep those copies in a bag other than the one carrying your passport. If you lose the real thing en route, it's got to be better than nothing...