You could use an IoC container to resolve the mapping for you by registering your own controller factory that allows the container to resolve the controllers - the container will resolve the controller type and inject a concrete instance of the interface.
Example using Castle Windsor
in global.asax in your MvcApplication class:
protected void Application_Start()
{
    RegisterRoutes(RouteTable.Routes);
    ControllerBuilder.Current.SetControllerFactory(new WindsorControllerFactory());
}
WindsorControllerFactory class
using System;
using System.Linq;
using System.Reflection;
using System.Web.Mvc;
using System.Web.Routing;
using Castle.Core.Resource;
using Castle.Windsor;
using Castle.Windsor.Configuration.Interpreters;
public class WindsorControllerFactory : DefaultControllerFactory
{
    WindsorContainer container;
    public WindsorControllerFactory()
    {
        container = new WindsorContainer(new XmlInterpreter(new ConfigResource("castle")));
        var controllerTypes = from t in Assembly.GetExecutingAssembly().GetTypes()
                              where typeof(IController).IsAssignableFrom(t)
                              select t;
        foreach (Type t in controllerTypes)
            container.AddComponentWithLifestyle(t.FullName, t, Castle.Core.LifestyleType.Transient);
    }
    protected override IController GetControllerInstance(RequestContext requestContext, Type controllerType)
    {
        // see http://stackoverflow.com/questions/1357485/asp-net-mvc2-preview-1-are-there-any-breaking-changes/1601706#1601706
        if (controllerType == null) { return null; }
        return (IController)container.Resolve(controllerType);
    }
}