JSONP does not force you to use eval. All that JSONP is doing is telling the web service to write JavaScript in such a way to immediately invoke a function with the name of the callback. Usually it's just called with a string. What you do with that string is up to you.
JSONP does force you to use eval, because JSONP means "instead of returning JSON for me to parse with a JSON library, return executable JavaScript for me to point at with the src attribute of a <script> element". The string consisting of the argument to the callback is de facto evaled by the user agent (when the executable JavaScript is executed) in order for it to become a JavaScript value at all.
The user agent evals the JSONP response before anything else happens: the server might return the string 'yourCallback({"JSON":"rocks!"});', which gets evaled to a function invocation whose argument is whatever the string '{"JSON":"rocks!"}' evals to. If that string doesn't successfully eval (as per the OP), your JSONP is broken.
Or, conversely, everyone here is confusing eval() with evaluation in general. JSONP does not call eval() as such, but it does evaluate the server response as JavaScript, because it ends up as:
<script src="/whatever?callback=foo"></script>
The source of which is something like
foo({"a":"b"})
Therefore, the hash supplied to foo() must be valid JavaScript.