Are linear combinations of powers of a matrix unique?

The situation is as follows: let $d$ be the degree of the minimal polynomial of $A$. Then the matrices $\{I,A,A^2,\dots,A^{d-1}\}$ are linearly independent and form a basis for the span of the powers of $A$.

In particular, this means that $A$ will have the uniqueness property you describe if and only if the minimal and characteristic polynomials coincide. That is, the following are equivalent:

1. The matrices $\{I,A,\dots, A^{n-1}\}$ are linearly independent
2. $\Bbb R^n$ is $A$-cyclic
3. $A$ is similar to a companion matrix
4. $A$ is non-derogatory
5. The minimal polynomial of $A$ is the same as its characteristic polynomial
6. The Jordan form of $A$ has one Jordan block for each eigenvalue
7. All eigenspaces of $A$ have dimension at most $1$
8. A matrix $B$ satisfies $AB = BA$ if and only if there is a polynomial $f(x)$ for which $B = f(A)$.

So, for example: any $A$ with $n$ distinct eigenvalues will have this property, and any $A$ which consists of a single Jordan block will have this property. Any diagonalizable $A$ with a repeated eigenvalue will not have this property.

Take $A=2I$ the identity matrix, $A^3=8I =2A^2$ so the coefficients are not unique.

Take $A$ nilpotent and not zero $A^3=0$, you have $A^3=0A^2=0A$.