Does whether or not we assume the Axiom of Choice change the definition of a set? A set is

...  is a well-defined collection of distinct objects, considered as an object in its own right. For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6} (from Wikipedia).

This means that $\{1, 1, 1, 1, 1, 1, ..., 2, 2, 2, 2, 2, 2, ..., 3, 3, 3, 3, 3, 3, ..., ...\}$ is the set $\{1, 2, 3, ...\}$, by definition. But, without the axiom of choice, how can we differentiate between the two? 

You're being confused by the difference between notation and what the notation stands for.
The ink blots (or pixels or whatever) that make up "$\{1,1,1,\ldots,2,2,2,\ldots, 3,3,3, \ldots\}$" are not what the set is -- they are merely part of a description of a set, and the set itself "doesn't know" how we have chosen to describe it.
What is a set, then?
Most fundamentally, a set is something we can ask, "is such-and-such one of your elements?" for every such-and-such we can think of, and get a "yes" or "no" answer back.  Nothing more, nothing less.
The axiom of extensionality asserts that if we're looking at two such things and they agree about what their elements are -- that is if we ask each of them "is such-and-such one of your elements?" about the same such-and-such, then they give the same answers -- then they are really just the same set. We could perhaps imagine that the set has two different phone numbers we can call to ask what its elements are, but unknown to us both numbers lead to the same call center. But (so says the axiom) all other sets do know this, and they will give us the same answer for $\{555,1,2,3,4\}$ as for $\{555,4,3,2,1\}$.
The notation $\{1,2,3\}$ stands for

a set that answers "yes" to "is $x$ one of your elements?" if $x=1$ or $x=2$ or $x=3$, and "no" otherwise.

The notation $\{1,1,\ldots,2,2,\ldots,3,3,\ldots\}$ is informal but would stand for something like

a set that answers "yes" to "is $x$ one of your elements?" if $x=1$ or $x=1$ or $x=1$ or ... or $x=2$ or $x=2$ or $x=2$ ... or $x=3$ or $x=3$ or $x=3$ ..., and "no" otherwise.

For every possible $x$, these two descriptions both demand the same answer, so they describe the same set.
