I think you can obtain an example by modifying the classical Toeplitz algebra. $\newcommand{\H}{\mathbf{H}}$ $\newcommand{\bT}{\mathbf{T}}$ $\newcommand{\cT}{\mathcal T}$ $\newcommand{\KH}{{\mathcal K}(\H)}$ $\newcommand{\BH}{{\mathcal B}(\H)}$
Recall that ${\mathcal T} \subseteq \BH$ where $\H=\ell^2({\mathbf N}_0))$ and $\cT/\KH\cong C(\bT)$. Let $q: \cT \to C(\bT)$ be the corresponding quotient homomorphism, let $J=\{ f\in C(\bT) \colon f(1)=0\}$ and let $\cT_0= q^{-1}(J)$. More concretely, $\cT_0$ is the set of closed algebra generated by all Toeplitz operators $T_f$ for which the symbol function $f$ belongs to $J$.
Since $\cT_0$ quotients onto the commutative ${\rm C}^*$-algebra $J$ it has loads of tracial states (just pull back the states on $J$).
On the other hand, suppose $a\in Z(\cT)$. Then $[a,k]=0$ for all $k\in \KH$. But it is standard and not too difficult to show that if $b\in\BH$ satisfies $[k,b]=0$ for all $k\in\KH$, then $b$ is a scalar multiple of the identity. Since $q(I_\H)\notin J$ the only possibility is that $a=0$.