I stumbled upon this question and I think I have an interesting answer.
I will make use of the FFT, please remark that in this argument I do not deal with the numerical error of the FFT but there are explicit error bounds on the FFT so they may be taken into account (you can find them in Higham, Accuracy and Stability...); moreover I will use the representation of Fourier Series with exponentials because it makes the argument easier.

I suppose we are on $[0,1]$ and I will work with the complex exponential basis. Let $\hat{f}(k)$ be the coefficients of the Fourier series with respect to the exponential basi.
Since $f$ is a trigonometric polynomial there exists a $K$ such that $\hat{f}(k)=0$ for $k>K$.

We observe now that $\hat{f'}(k)=2\pi i k \hat{f}(k)$. Therefore,

$$||f'||_{\infty}\leq 2\pi K \sum_{-K}^K |\hat{f}(k)|. $$

We now run the inverse FFT of size M bigger than K on the $\hat{f}(k)$.
The inverse Fast Fourier Transform using the Cooley-Tuckey algorithm is fast and numerically well behaved and gives us the value of the
trigonometric polynomial at $M$ equispaced points, call them $x_1, \ldots, x_M$.

Then
$$
\max_{i=1,\ldots, M} f(x_i)\leq \max f(x)\leq \max_{i=1,\ldots, M} f(x_i)+ 2\pi \frac{K}{M} \sum_{-K}^K |\hat{f}(k)|.
$$

There are some normalizations involved in the FFT, but the argument should work.