Here is how I would approach the problem, although there may be a more clever method.
We will restrict our view to the interval $I=(-\frac{\pi}{2}, \frac{\pi}{2})$. Since $p$ is a polynomial, it must be continuous on the closure $\overline{I}=[-\frac{\pi}{2}, \frac{\pi}{2}]$. By the extreme value theorem, $p$ attains both a maximum and a minimum on $\overline{I}$. Therefore, there is some $m\in \mathbb{R}$ such that for all $x\in I, |p(x)|\leq m$.
On the other hand, $tan(x)$ is not bounded on $I$ and has the range $(-\infty, \infty)$.
Let $n=2m$. There exists some $x$ such that $tan(x)=n$. For this fixed $x$, $f(x)=tan(x)-p(x)\geq tan(x)-m=m\geq 0$. Similarly, there exists an $x$ such that $tan(x)=-n$. For this fixed $x$ we have $f(x)=tan(x)-p(x)\leq tan(x)+m=-m\leq 0$.
From the equations above, we see that there is and $x$ such that $f(x)\geq 0$ and an $x$ such that $f(x) \leq 0$. As you suggested, this is where we can apply the intermediate value theorem. $f$ is continuous on $I$ and attains values above and below $0$ so there must be some $x'$ between the two $x$ we found such that $f(x)=0$.