If you want to change what people in everyday life call you, then yes, that's not paperwork, that's just a polite request/conversation with various people (and, hopefully, they respect it).
If you want to change the name by which organizations, including the government, refer to you, then that is _by definition_ paperwork. I simply don't believe that you could have done that without submitting forms or other types of paperwork, at any point in recent history - pre- or post-9/11.
Some hyperbole on my part, sorry. I really meant "official name changes, getting permission from courts etc").
About 30 years ago I married and my wife and I changed our names significantly. California marriage licenses don't mention married names at all. At the time the name law was "you may use any name you want, but may not use your name to commit fraud". Here's what I remember we did, I remember being surprised at how easy it was:
Went to the DMV and said "I want a different name on my DL". Filled out a DL application, handed over the old one and they sent me a new one. No proof of anything required. No birth cert or anything else.
Visited my (small) bank, told them I'd changed my name, showed them the DL and they changed it.
Called the credit card companies and said "please send me my cards in a different name." I recently checked my credit rating and the old name does appear in the "also known as" section (as well as various typos of it and my new name).
Went to the Social security office and they did want to look at my old SS card and my new DL. But that was all -- filled out the "order a replacement card" form and it came in my new name.
I went to the consulate of my (small) country and told them I wanted a different name. I did hand over my marriage license but as it was silent on the topic it didn't help. The consul called my mother who confirmed the change. The consul said "I could hear her eyes rolling through the phone". But they issued me a new passport, which I have renewed several times at different consulates in different countries without issue. Note: had I done this back home I don't think I would have gotten away with it. There the name change is complicated and they issue you a whole new birth certificate!
My wife went to the consulate of her (large and bureaucratic) country. At the time a change like we wanted was not even legal. But as we'd married in the USA they just accepted it as a "local law" change and issued her a new passport which she has also renewed several times without issue.
I never changed the name on my green card and have never had a problem even though it doesn't match my passport. My (now ex) wife's green card was issued in the name in her passport and no proof was ever asked to link the name change, though she may have submitted the marriage license.
We did this all casually over a year or so, though used our new names immediately. There was no rush, and back then people rarely asked for ID anyway so I don't remember anyone ever noticing that I had documents in different names (e.g. CC and DL).
If you want to change what people in everyday life call you, then yes, that's not paperwork, that's just a polite request/conversation with various people (and, hopefully, they respect it).
If you want to change the name by which organizations, including the government, refer to you, then that is _by definition_ paperwork. I simply don't believe that you could have done that without submitting forms or other types of paperwork, at any point in recent history - pre- or post-9/11.
What am I misunderstanding?