So this is sort of silly, considering I'm getting the info from an unsourced George Carlin book (fairly sure it was Brain Droppings, but maybe Napalm & Silly Putty), but he states indigenous Americans are not called Indians because Columbus thought he landed in India. He claims back then, India was called Hindustan, and Columbus called the natives "a people in God" (even though they were considered heathens) which translates to "un pueblo en Dios", and the "en Dios" part is the origin of "Indian" to describe Americans.
So... does any sort of record exist proving this correct? What is the etymology of the word "Indian" or "India"?
"Hindustan" was the name by which the Persians referred to India. The original Sanskrit name of the river Indus is "Sindh", which was changed to "Hind" in Persian. The suffix "-stan" has old Indo-European origins -- "sthan" in Sanskrit, "-stan" in Persian, both meaning "place" or "land". So "Hindustan" literally meant "the land beyond the Indus river".
The word "Hindustan" was really popularized by the Mughals, who first came to India in 1526, which is a bit late considering your Columbus reference. At the time, "Hindustan" was still an uncommon word in India itself, but certainly Persians were using it at the time. So it's possible that the Persian word was known in Europe, via the Arabs.
However, the Indians' own name for India was "Bharat", which goes back at least 2500 years, and probably more. Bharat is mentioned in the Puranas, and was widely used to refer to India during the time of the Mauryan empire. It included Pakistan and Bangladesh (pre-partition India) as well as Afghanistan. The word goes back to "Bharata", a king mentioned in the Rig Veda, about 3500 years old. Even when Mughals ruled India and popularized the word "Hindustan", most Indians continued to refer to their country as "Bharat" and still do to this day.
The theory you mentioned sounds wrong. "India" has a similar origin to "Hindustan", meaning "the land of the Indus". This was well known in Columbus' time.
As far back as the 5th century BC, Herodotus referred to India as "Indoi" - "the land of the Indus", or "Indos" to mean "an inhabitant of Indoi". In the English language, the name "India" specifically goes back to at least Alfred the Great's time (9th century). It fell out of favor for a few centuries under French influence (when it was referred to as "Inde"), but returned to "India" from about the early 17th century. It was understood as "land of the Indus river".
The first Europeans to establish a sea route around the Cape of Good Hope to trade directly with South East Asia were the Portuguese in 1497. They referred to the whole area, from current day Indonesia, Timor, Malaysia etc to India, Pakistan and surrounding countries as the Indies, from the earlier established usage derived from references to the Indus river. As late as the 1860s official British documents referred to military service during the Indian Mutiny as service in Bengal East Indies. So Europe referred to all of the spice rich areas of South East Asia as the Indies. This is the area that Columbus was trying to reach by sailing West instead of East, and the area he claimed to have reached. The Indies was already a well established name for the area Columbus was seeking, well before his expedition.
So the area Columbus did reach is now referred to as the West Indies, the old Indies are referred to as the East Indies and Columbus referred to the inhabitants of his new discovery as Indios or Indians.