A density proof not via Stone-Weierstrass Context: I have proved Weierstrass' theorem (polynomials are dense in $C[a,b]$) in two ways: one using Bernstein polynomials, and one using convolutions. You can also use Stone-Weierstrass theorem, however I do not quote that result since I have not proved it.
My question, however, is of a different nature: I am not allowed to use Stone-Weierstrass, but am asked to prove the following:

Given a continuous function $f \in C(\mathbb R)$ such that $\lim_{|x| \to \infty} f(x) = 0$, and given $\epsilon>0$, there exists a polynomial $p$ such that $|f(x) - p(x)e^{-|x|}| < \epsilon$ for all $x \in \mathbb R$. Which is to say, the set $\{ p(x)e^{-|x|} : p \in \mathscr P\}$ is dense in the set of continuous functions on $\mathbb R$ decaying to zero (in the supremum norm).

You cannot try to approximate $f(x)e^{|x|}$ by polynomials, because that will give you a right side bound dependent on $x$, which is not the case in uniform convergence. Furthermore, working over $\mathbb R$, breaking it into compact intervals and applying Weierstrass is getting me nowhere.
Hence, I need help on this question. I request an incomplete "fill-in-the-blank" answer, if that's possible!
 A: Consider using the power series for $e^{|x|} = \sum_{n\ge0} \frac{|x|^n}{n!}$ and use the fact that partial sums are polynomials and they converge uniformly in compact sets. Such a partial sum combined with $e^{-|x|}$ will be almost $1$ for a sufficiently large set.
A: .All right, here is the answer.
I'll restrict myself to $[0,\infty)$, and so the set to be shown dense in the question will become $p(x)e^{-x}$. A similar proof will follow for the other space.
Note that $\{p(x)e^{-x}\}$ doesn't span $C_0[0,\infty)$ if and only if there is a non-zero linear functional $L$ over $C_0[0,\infty)$ , on whose application, all functions of the form $p(x)e^{-x}$ vanish. (This is by the Hahn-Banach theorem).
What is a linear functional over $C_0 [0,\infty)$? Well, it corresponds to some measure (with some other properties like regularity which I will ignore) $\mu$, that is to  say,  there exists a measure $\mu$ so that $$L(f) = \displaystyle\int_{0}^\infty f d\mu$$
for all $f \in C_0[0,\infty)$. This follows from the Riesz-Markov-Kakutani theorem, although not used in it's full strength.
Now, all we need to do, is to push this measure to $(0,1]$. That is to say, we have a homeomorphism from $[0,\infty)$ to $(0,1]$, given by $x \to e^{-x}$, which pushes the measure $\mu$ into a measure $\nu$ on $(0,1]$ (in a manner which I leave the reader to figure out, it's called the push-forward of a measure).
Now, if one does this, it will be found, after explicit computation of the push-forward, that $\displaystyle\int_0^1 p(x)d\nu = 0$ for all polynomials $p$. Then, by the uniqueness of moment theorem for bounded sets (because $[0,1)$ is bounded), it will follow that $\nu \equiv 0$, so $\mu \equiv 0$, so $L \equiv 0$, showing the density of the given set.

Alternatively, I have used a technique and computation similar to the one showed in an answer above, to see that it is enough that $e^{-\lambda x}, \lambda > 0$ be dense in $[0,\infty)$. This then will follow from a similar logic to above, but the computations are much easier. 
