1) No. Any choice of basis determines an endomorphism that the matrix corresponds to and in general different choices of basis will give different endomorphisms. (They are, of course, all similar.)
2) No. Consider the case that $A$ is not diagonal. Two matrices have the same entries if and only if they represent the same linear transformation with respect to a fixed basis.
3) No. This is the same question as 1).
4) To see this concretely, write out the condition $AS = SD$ for $D$ a diagonal matrix explicitly. To see this abstractly, let $T$ be a linear transformation with respect to a basis $e_i$, and suppose it has a basis $v_i$ of eigenvectors with eigenvalues $\lambda_i$. Then $T$ is diagonal with respect to the basis $v_i$. If $S$ denotes the linear transformation which sends $v_i$ to $e_i$, then
$$STS^{-1}(e_i) = ST v_i = S \lambda_i v_i = \lambda_i S v_i = \lambda_i e_i$$
so $STS^{-1}$ is diagonal with respect to the basis $e_i$. Now, the above is a statement about linear transformations which is independent of basis. Writing everything above in terms of the basis $e_i$ gives you a corresponding statement about matrices, and in that statement $S^{-1}$ is more or less by definition the matrix whose columns are the entries of $v_i$ (with respect to the basis $e_i$).
I have often thought that elementary linear algebra would be less confusing if it were made explicit that when changing bases one is really working with two vector spaces; first the original vector space $V$ one cares about and second the concrete vector space $\mathbb{C}^n$ where $n = \dim V$ with its distinguished basis. A basis for $V$ is then equivalent to the choice of an isomorphism $f : \mathbb{C}^n \to V$ and changing bases corresponds to changing the choice of this map. Crucially, there are two natural ways to do this: either precompose with an automorphism $\mathbb{C}^n \to \mathbb{C}^n$ or postcompose with an automorphism $V \to V$. The two give the same result, but the notion of sameness here is itself dependent on the choice of $f$.
In category theory, one says that the finite-dimensional vector space (over a fixed field) of a given dimension is unique up to isomorphism, but not unique up to unique isomorphism, and so when identifying different vector spaces one must keep track of the identifications one is using or else risk getting hopelessly lost.
In other words, when dealing with objects that are isomorphic but for which the isomorphism is not unique, it is better to behave as if they are different objects even if they are in some sense "the same."
It might help to think of the same linear transformation with respect to two different bases as operating on two different data types. That is, with respect to a given basis $\mathcal{B}$, the corresponding matrix should perhaps be thought of as a function which accepts and spits out "$\mathcal{B}$-type" vectors, and with respect to a different basis $\mathcal{C}$ accepts and spits out $\mathcal{C}$-type vectors. These operations are compatible but to specify the compatibility you need to typecast from $\mathcal{B}$-type vectors to $\mathcal{C}$-type vectors and back again, and this is exactly what the change-of-basis matrix is supposed to do.
The change-of-basis matrix therefore has different input and output types.
Best Answer
You should write the precise data, but some generalities can be say.
If your initial matrix is, say $A$ and the matrix of the change of basis is $B$ then the version of $A$ in this new basis is $B^{-1}AB$.
If you want to diagonalize (or almost diagonalize) $A$ then choosing the eigenvectors of $A$ as the basis change with matrix $C$, then $C^{-1}AC$ would be diagonal or almost diagonal.
Edit: Take $A=\left[\begin{array}{cc}1&2\\2&5\end{array}\right]$ and the basis change: $$b_1=2e_1+3e_2,$$ $$b_2=2e_1-3e_2,$$ then $B=\left[\begin{array}{cc}2&2\\3&-3\end{array}\right]$ and $B^{-1}AB=\frac{1}{48}\left[\begin{array}{cc}7&11\\10&18\end{array}\right]$.
This can be interpreted as if $A$ determine a linear transformation $\mathbb R^2\to\mathbb R^2$ then $B^{-1}AB$ represents the very same transformation but after the basis change in both domain and codomain.
In the case you take eigenvectors from $A$ any choice of them will do the analogous effect but nearing to its diagonalization.