The fact that a page is being served up with a 404 error means that responsible web indexes will not be storing the 404 page itself anyway. That is what the HTTP status code is for - the number 404 isn't there for the user's benefit! As far as removing the original page from an index, it would be better to make resources which are truly gone return an error
410 Gone instead.
Regarding the second part of your question, please do not rewrite the URL. This is incredibly user-hostile; if someone opens up a link in a background tab that happens to have gone invalid, a rewritten URL means that there is no way for them to figure out what the intended URL was, and thus no way for them to know what page had the problem. It's especially bad if the rewritten URL goes to an entirely different domain; I have recently seen certain cheap hosting providers do this for things like bandwidth overage error pages and it does nobody any favors. Also, if you redirect on 404, the resulting page might not be served up with a 404 status, meaning that the page then might end up being indexed anyway.
If the URL is no longer valid because the content has simply been moved to another location, consider redirecting the old URL to the new one (or its closest equivalent); that way, the old URLs are still useful from other locations, and will eventually be replaced with the new URLs in search indexes.