Is every invertible matrix a change of basis matrix?

Yes. If $S$ is an invertible matrix, then its columns will be the other basis, as for the standard basis $e_1,\dots,e_n$, we have $\ Se_k=$ the $k$th column of $S$.

Say $b_k:=Se_k$. Then for a linear transformation $A$, the value $ASe_k$ is the image of $b_k$ under $A$, and for a vector (given in standard coordinates), $S^{-1}v$ will give its coordinates in the basis $(b_1,\dots,b_n)$

because if $v=\lambda_1 b_1+\dots+\lambda_n b_n$, then, as the columns of $S$ are just the $b_k$ 's, this equation becomes $\ v=S\cdot\pmatrix{\lambda_1\\ \vdots\\ \lambda_n}$.

Yes it is. Any invertible matrix $\mathbf{A}$ is the change of basis of the basis formed by the columns of $\mathbf{A}$ (which is a basis because $\mathbf{A}$ is invertible) to the canonical basis.