This solution doesn't need web.config file changes or catch-all routes. 
First, create a controller like this;
public class ErrorController : Controller
{
    public ActionResult Index()
    {
        ViewBag.Title = "Regular Error";
        return View();
    }
    public ActionResult NotFound404()
    {
        ViewBag.Title = "Error 404 - File not Found";
        return View("Index");
    }
}
Then create the view under "Views/Error/Index.cshtml" as;
 @{
      Layout = "~/Views/Shared/_Layout.cshtml";
  }                     
  <p>We're sorry, page you're looking for is, sadly, not here.</p>
Then add the following in the Global asax file as below: 
protected void Application_Error(object sender, EventArgs e)
{
        // Do whatever you want to do with the error
        //Show the custom error page...
        Server.ClearError(); 
        var routeData = new RouteData();
        routeData.Values["controller"] = "Error";
        if ((Context.Server.GetLastError() is HttpException) && ((Context.Server.GetLastError() as HttpException).GetHttpCode() != 404))
        {
            routeData.Values["action"] = "Index";
        }
        else
        {
            // Handle 404 error and response code
            Response.StatusCode = 404;
            routeData.Values["action"] = "NotFound404";
        } 
        Response.TrySkipIisCustomErrors = true; // If you are using IIS7, have this line
        IController errorsController = new ErrorController();
        HttpContextWrapper wrapper = new HttpContextWrapper(Context);
        var rc = new System.Web.Routing.RequestContext(wrapper, routeData);
        errorsController.Execute(rc);
        Response.End();
}
If you still get the custom IIS error page after doing this, make sure the following sections are commented out(or empty) in the web config file: 
<system.web>
   <customErrors mode="Off" />
</system.web>
<system.webServer>   
   <httpErrors>     
   </httpErrors>
</system.webServer>