This is trivial with ordinary Bernstein polynomials --- it requires calculating only one Bernstein coefficient --- but can require a polynomial of inordinate degree because of Bernstein polynomials' slow convergence rate. For example, if $\epsilon=0.01$ and $f$ is Lipschitz with constant 1, the required polynomial degree is 11879. (I would also accept approximating $f$ with a rational function instead, but that's outside the scope of this question.) (4/4)

And as you mentioned, "rounding" the Chebyshev coefficients or "nodes" to rational numbers would add a non-trivial error not accounted for in your answer's error bound. **** Here is the use case I care about in this question: Approximate Bernoulli Factories, or tossing heads with probability equal to a polynomial in Bernstein form that comes within $\epsilon$ of a continuous function $f(x)$. (3/4)

Unlike with rational arithmetic (where arbitrary precision is trivial thanks to Python's fractions module), transcendental and trig. functions require special measures to support arbitrary accuracy, such as constructive/recursive reals --- floating-point won't do for my purposes. Also, I might have to work with polynomials of arbitrary degree, including degree 1000 or even higher; the Chebyshev-to-Bernstein conversion seems to be quadratic in the polynomial degree (due to the matrix size). (2/4)

Thank you for responding. I am still hesitant on using a conversion from Chebyshev to Bernstein form unless someone convinces me that Micchelli's polynomials, the Lorentz operator (which I have already implemented in Python), or Günturk and Li's paper is harder to implement — especially because they naturally don't involve transcendental or trigonometric functions — and I would still rather see whether there are upper bounds for the constants in those methods. (1/4)

On your first comment: At this point I would rather see if there are upper bounds for the constant factors given in the papers I listed in my question (e.g., Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li; numerous lemmas in Holtz et al.). My implementation attempts have shown that Chebyshev polynomials are far from being "readily convertible" to Bernstein form (first vs. second kind; $[0, 1]$ vs. $[-1, 1]$; Chebyshev points vs. Chebyshev coefficients; etc.) Thus, I will consider Chebyshev polynomials as a last resort.

For the Lorentz operator, see also my Python implementation.

I thought of Chebyshev approximation then conversion to the Bernstein basis (e.g., using the paper of Rababah 2003). But what I had in mind when I spoke of polynomials that are "readily convertible" to Bernstein form includes polynomials formed with the Lorentz operator (Holtz et al. 2011), which doesn't rely on trigonometric functions, but only on rational arithmetic. Other examples include the iterated Bernstein operator in the Guan paper, or the one-bit polynomials in Güntürk and Li (which are already in Bernstein form).