If a matrix commutes with a set of other matrices, what conclusions can be drawn?

Call your four matrices $A,B,C,D$ respectively. While they indeed don't span $M_4(\mathbb C)$, the point is that the algebra they generate is the whole matrix space. So, any matrix that commutes with $A,B,C,D$ must in turn commute with all members of $M_4(\mathbb C)$. In fact, if we put $X=\frac{B\,(AC-C)\,A}{2i}$ and $Y=\frac{B\,(AC+C)\,A}{2i}$, the canonical basis of $M_4(\mathbb C)$ can be obtained as polynomials in $A,B,C,D$: \begin{align*} E_{11}&=\frac12(X^2+X),&E_{14}&=E_{11}B,&E_{13}&=E_{11}D,\\ E_{22}&=\frac12(X^2-X),&E_{23}&=E_{22}B,&E_{24}&=-E_{22}D,\\ E_{33}&=\frac12(Y^2+Y),&E_{32}&=-E_{33}B,&E_{31}&=-E_{33}D,\\ E_{44}&=\frac12(Y^2-Y),&E_{41}&=-E_{44}B,&E_{42}&=E_{44}D,\\ E_{12}&=E_{13}E_{32},\\ E_{21}&=E_{24}E_{41},\\ E_{34}&=E_{31}E_{14},\\ E_{43}&=E_{42}E_{23}. \end{align*}

Consider the matrix $$ A=\begin{bmatrix} a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44} \end{bmatrix}. $$

Then, if $A$ commutes with your first matrix, then $$ \begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&-1&0\\ 0&0&0&-1 \end{bmatrix}\begin{bmatrix} a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44} \end{bmatrix}= \begin{bmatrix} a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ a_{31}&a_{32}&a_{33}&a_{34}\\ a_{41}&a_{42}&a_{43}&a_{44} \end{bmatrix} \begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&-1&0\\ 0&0&0&-1 \end{bmatrix} $$ In other words, $$ \begin{bmatrix} a_{11}&a_{12}&a_{13}&a_{14}\\ a_{21}&a_{22}&a_{23}&a_{24}\\ -a_{31}&-a_{32}&-a_{33}&-a_{34}\\ -a_{41}&-a_{42}&-a_{43}&-a_{44} \end{bmatrix}= \begin{bmatrix} a_{11}&a_{12}&-a_{13}&-a_{14}\\ a_{21}&a_{22}&-a_{23}&-a_{24}\\ a_{31}&a_{32}&-a_{33}&-a_{34}\\ a_{41}&a_{42}&-a_{43}&-a_{44} \end{bmatrix} $$ This tells you that $a_{31}=0=a_{32}=a_{41}=a_{42}=a_{13}=a_{14}=a_{23}=a_{24}$. Already, $A$ is significantly simplified. The second matrix gives $a_{11}=a_{33}$, $a_{12}=a_{34}$, $a_{21}=a_{43}$, and $a_{22}=a_{44}$. Then, keep going.

For the example you gave, the conclusion follows from Schur's Lemma since the gamma matrices form an irreducible representation of the complexification of the Clifford algebra $Cl_{1,3}(\mathbf{R})_{\mathbf{C}}$. This comes up when considering irreducible representations of the Lorentz group (specifically the spin representation), which is central to discussions of spin in physics.