Most of the answers already take the whole structure of the complex numbers as given. Therefore let me go to a more elementary level, where we don't yet assume anything about the complex numbers except that they contain the real numbers, and at least one additional number $i$ which solves the equation $x^2+1=0$.
Now consider the equation $x+i=0$. I think you would agree that a set of numbers where we could not solve this equation would not be terribly useful. By definition, we denote the solution of $x+a=0$ with $-a$, so the solution here is $-i$. However that's up to now only a notation; for example, the same way we get $-0$, which we know is the same as $0$. Therefore the question is: What is $-i$?
First, we note that $-i$ cannot be a real number, because otherwise $i$ would be its negative (also a real number), and we already know $i$ is not a real number. So there remain two possibilities: Either $-i=i$, or $-i$ is a different non-real number than $i$.
We also want that the distributive law continues to hold.
Now assume $-i=i$, that is, $i+i=0$. Then we have $-2 = (-1) + (-1) = i^2 + i^2 = i(i+i) = i\cdot 0 = 0$. Now that's obviously wrong, therefore we cannot have $-i=i$. Thus $-i$ is a distinct number from $i$.
Edit: On A.P.'s request, I also add the proof that $-i=(-1)i$.
To prove that $-i=(-1)i$ means to prove that $i+(-1)i=0$, because that's how $-i$ is defined.
We obviously have, using the fact that $x=1x$ for all $x$:
$$i +(-1)i = 1i + (-1)i =(1+(-1))i = 0i = 0$$
Note that you can prove essentially the same way that $i(-1) = -i$ (in case you take into account that multiplication might not turn out to be commutative, which actually would not be that unusual, although for complex numbers multiplication actually is commutative)- Therefore you also get
$$(-i)^2+1 = i(-1)(-1)i+1 = i^2+1 = 0$$
Now for the proof of $(-1)i=-i$ as well as above when proving $-i\ne i$, I've used $0i=0$, which seems obvious, but to be sure, let's prove this as well. We have
$$0i = (0+0)i = 0i+0i$$
Now we add $-(0i)$ to both sides of the equation (remember, the demand that for each $x$ we have a $-x$ which fulfils $x+(-x)=0$ was how we arrived at $-i$ at the first place), to get for the left hand side $0i + (-(0i)) = 0$, and for the right hand side $0i + 0i + (-(0i)) = 0i + 0 = 0i$ (note that in this, I've made another assumption, namely that addition is still associative even if expressions with $i$ are involved; but that's also a natural assumption which you'd not give up unless necessary).
Note that ultimately, all I needed was
- the rules for real numbers continue to hold unchanged
- the fact that $i$ solves the equation $x^2+1=0$
- the associativity of addition
- $x+0=0$ for all $x$
- the existence of an additive inverse $-x$ for any number $x$
- the associativity of multiplication
- $1x=x$ for all $x$
- the distributive law
The first two are given by the problem, while the rest are very fundamental assumptions which you wouldn't give up lightly.