Eval is considered evil for all but one specific case, which is your case of generating programs during runtime (or metaprogramming). The only alternative would be to write your parser/interpreter (which can be done relatively easily in javascript, but rather for a simpler language than javascript itself - I did it and it was fun). Thus using eval() function here is legitimate (for making a browser-side compiler to a reasonably fast code, you need to use eval for generated compiled javascript anyway).
However, problem with eval is security, because evaluated code has the same privileges and access to its environment as your script that runs it. This is a topic quite hot recently and EcmaScript 5 was designed to partially address this issue by introducing strict mode, because the strict-mode code can be statically analyzed for dangerous operations.
This is usually not enough (or problematic for backward compatibility reasons), so there are approaches like Caja that solves security by analyzing the code on a server and allows only strict safe subset of javascript be used.
Another often used approach is protect the user, but not protecting from malicious attacks using running the user generated javascript in an <iframe> element embedded in the parent page (usually used by sites like jsfiddle). But it is not secure for the iframe can access its parent page and get to its content.
Even in this iframe approach there has been some progress recently e.g. in chrome to make it less vulnerable by using sandbox attribute
<iframe src="sandboxedpage.html" sandbox="allow-scripts"></iframe>
where you can even specify different privileges.
Hopefully, we will have an easy way to use safe and easy metaprogramming soon, but we are not there yet.