I'm confused.
Realizing $\mathbb{F}_4=\mathbb{F}_2[T]/(T^2+T+1)$, the polynomial $X^4+X^3+1$ splits as $(X^2+TX+T)(X^2+(T+1)X+T+1)$.
These 2 factors have no root over $\mathbb{F}_4$, so they're irreducible, so our Galois group has order 2 or 4. Since the Galois group of a finite field is cyclic and considering the cyclic subgoups of $S_4$, the only possibility is that it is generated by $(12)(34)\in S_4$.
So our Galois group has order 2 and everything should split after adjoining one of the roots. But after adjoining a root of say $X^2+TX+T$ to $\mathbb{F}_4$, I can't seem to find a root of $X^2+(T+1)X+T+1$?
Let $A$ be a root of $X^2+TX+T=0$, then $$X^2+TX+T = (X+A)(X+A+T)$$ in characteristic $2$. Now apply the Frobenius automorphism $\sigma(X)=X^2$ to $A$ and $A+T$. You get $$\begin{align}\sigma(A)&=TA+T\\ \sigma(A+T)&=TA+1\end{align}$$ and indeed $$X^2+(T+1)X+(T+1)=(X+TA+T)(X+TA+1)$$ so $\sigma(A)$ and $\sigma(A+T)$ are the required roots. You can easily verify that $\sigma$ has order $4$ over $\mathbb{F}_2$ and corresponds to $(1234)\in S_4$. Then $\sigma^2$ is a Frobenius automorphism over $\mathbb{F}_4$ and corresponds to $(13)(24)$.