As you said in the comments, one direction is Stone-Weierstrass. For the other direction, suppose $A$ is a dense subalgebra of $C(X)$, and let $x,y\in X$. Take any function $f\in C(X)$ such that $f(x)\neq f(y)$ (e.g., using Urysohn's Lemma).
By density of $A$, there exists $g\in A$ such that $\Vert g-f\Vert_{\infty}<|f(x)-f(y)|/2$, where $\Vert\cdot\Vert_\infty$ is the uniform norm. Then
$$|g(x)-f(x)|\leq\Vert g-f\Vert_\infty<|f(x)-f(y)|/2$$ so
$$|g(y)-f(x)|\geq |f(x)-f(y)|-|f(y)-g(y)|>|f(x)-f(y)|/2,$$
thus $g(x)\neq g(y)$, so $A$ separates points of $X$.
Hint: If $\sup_{x \in [-1,1]} |\,p(x) - f(x)|<\epsilon$ then
$\sup_{x \in [-1,1]} |\,\frac{1}{2}(\,p(x)+ p(-x)\,)- f(x)\,|<\epsilon$
$\bf{Added:}$
Let $p(x)$ a polynomial so that for every $x \in [-1,1]$ we have $|\,p(x) - f(x)|<\epsilon$. Note that if $x \in [-1,1]$ then also $-x \in [-1,1]$. So we have
$$|\,p(x) - f(x)|<\epsilon\\
|\,p(-x) - f(-x)|<\epsilon$$
Add up the inequality and divide by $2$:
$$\frac{1}{2} ( |\,p(x) - f(x)| + |\,p(-x) - f(-x)|) < \epsilon$$
Note that we have $|a+b| \le |a|+|b|$ for all numbers. Therefore we get
$$\frac{1}{2} \cdot |(p(x) + p(-x) ) - (f(x) + f(-x) ) | < \epsilon$$
or
$$ |\frac{1}{2}\cdot (p(x) + p(-x) ) - \frac{1}{2}\cdot(f(x) + f(-x) ) | < \epsilon$$
$\tiny{\text{ the averages also satisfy the inequality }}$.
Now since $f$ is even we have $\frac{1}{2}\cdot(f(x) + f(-x) ) = f(x)$.
Moreover, $\frac{1}{2}\cdot (p(x) + p(-x) )$ is an even polynomial already. We are done.
Best Answer
The algebra of polynomials is just the algebra generated by the single function "$x$", i.e. the inclusion map from your interval into $\mathbb{R}$. So you can pick some other continuous function instead and take the subalgebra it generates. As long as your function is injective, this subalgebra separates points and so is dense by Stone-Weierstrass, and typically this subalgebra will not contain any nonconstant polynomials. For example, you could take the subalgebra generated by the exponential function, which concretely consists of functions of the form $$x\mapsto\sum_{k=0}^na_ke^{kx}$$ for some constants $a_k$.
A related example which actually is used a lot (in connection with Fourier analysis) is the algebra of trigonometric polynomials, i.e. the subalgebra generated by the sine and cosine functions (which will jointly separate points as long as your interval has length less than $2\pi$). If you consider complex-valued functions instead of real-valued functions, this can also be described as the subalgebra generated by $x\mapsto e^{ix}$ and $x\mapsto e^{-ix}$ (so, it is just like the exponential example above except that there is a factor of $i$ in the exponents and $k$ can range over negative integers too).