In Anglo-American common law, your identity is basically whatever it is you call yourself, provided that you are not doing so with intent to defraud or otherwise facilitate unlawful activities. Most U.S. states still recognize a common law name change or assumed name.

If James McGill uses the name "Saul Goodman" openly and notoriously in the course of his business, he could reasonably use either name, or both, to identify himself. It is literally just that simple. Your name is whatever you use as your name. If you are a corporation, you may need to file a "doing business as" document with the state business registration authority, but natural persons can merely start introducing themselves with the new name. I could start calling myself "Master President Jack Redbull Walks-Away-From-Explosions Cartman the 42nd", in addition to my birth name and my HN handle, and lo, that would be my name.

As such, the "proof" would be as simple as solemnizing an affidavit that you are not using the name for any malicious purpose.

Requiring an ID--or more specifically, a state-issued ID--is much more burdensome. The state, you see, has a selfish interest in being able to link all of the names a person may have, such that it is easier to enforce its laws upon that person.

I could not go to the state's ID-issuing agency and get an ID card featuring the name "Master President Jack Redbull Walks-Away-From-Explosions Cartman the 42nd". The bureaucrat on site would rather tiresomely insist upon knowing the boring old name that my parents gave to me, and adamantly maintain that the state will officially recognize only one name at a time, that requires a form to be filled out and authorized by a probate judge, and the new name wouldn't fit on the card anyway, and would have to be abbreviated to "[Mr.] Master P. Cartman, 42nd".

This common law tradition allows a person to use an assumed name or pseudonym for travel, without the expectation that the traveler be authorized in any way. But the state (apparently) has an interest in tracking the whereabouts of criminals and those who appear to have criminal intent. So it institutes ID requirements to slide around the common law right of people to avoid name-based tracking regimes.

I imagine if you were ever on TV or in the newspaper/a magazine with your picture in it, you can just carry the newspaper around with you everywhere and show them that picture.

I think someone like Barack Obama or Al Pacino can easily "prove their identity".

I guess it depends what point you're trying to make. There's a big debate in several states around voting and whether it should require proof of identity and whether that's specifically an ID or something else.

I personally think there's a difference between "you must have one of these specific documents to travel" vs "you must be an identifiable person to travel"