As others mentioned - there is no way to do it `the way you're doing it'...   
a) You need contravariance - for the Add to work  
b) You need covariance to be able to upcastfrom IResponseHandler<TResponse> to IResponseHandler<IResponse> 
(also you have another compilation problem with returning out into differnt type of List which cannot work either way)...  
For a solution - you could trick it into working sort of - if this contract satisfies what you need. It's more of a 'practice example' as you lose some of the support - but depends on what you need...  
interface IResponse { }
interface IResponseHandler<out TResponse>
    where TResponse : class, IResponse
{
    // add 'read-only' (simplified) properties only - that support 'covariance' - meaning no 'input parameters' of T etc.
    // void Handle(TResponse response);
}
abstract class ResponseHandler<TResponse> : IResponseHandler<TResponse> 
    where TResponse : class, IResponse
{
    public abstract void Handle(TResponse response);
}
class TestHandler
{
    private static Dictionary<Type, List<IResponseHandler<IResponse>>> _handlerMap = new Dictionary<Type,List<IResponseHandler<IResponse>>>();
    public static void AddResponseHandler<TResponse>(IResponseHandler<TResponse> handler) where TResponse : class, IResponse
    {
        List<IResponseHandler<IResponse>> handlers;
        _handlerMap.TryGetValue(typeof(TResponse), out handlers);
        if (handlers == null)
        {
            handlers = new List<IResponseHandler<IResponse>>();
            _handlerMap.Add(typeof(TResponse), handlers);
        }
        IResponseHandler<IResponse> myhandler = handler;
        handlers.Add(myhandler);
    }
    public static void Handle<TResponse>(TResponse response) where TResponse : class, IResponse
    {
        List<IResponseHandler<IResponse>> handlers;
        _handlerMap.TryGetValue(typeof(TResponse), out handlers);
        if (handlers == null) return;
        foreach (var handler in handlers)
        {
            (handler as ResponseHandler<TResponse>).Handle(response);
        }
    }
}
// and implementation...
class FirstResponse : IResponse { }
class AutomatedResponse : IResponse { }
class FirstHandler : ResponseHandler<FirstResponse>
{
    public override void Handle(FirstResponse response) { }
}
class AutomatedHandler : ResponseHandler<AutomatedResponse>
{
    public override void Handle(AutomatedResponse response) { }
}
// ...and a test...
var firsthandler = new FirstHandler();
var secondhandler = new AutomatedHandler();
TestHandler.AddResponseHandler(firsthandler);
TestHandler.AddResponseHandler(secondhandler);
var first = new FirstResponse();
var second = new AutomatedResponse();
TestHandler.Handle(first);
TestHandler.Handle(second);
There are couple things of interest, fast...  
1) You need out on the base interface - to make it covariant 
2) You need to keep it covariant - by not adding anything in it like Add (see the comment). Basically (and overly simplified) you need to maintain it read only (mark that this isn't true - just easier to think that way). Also that goes for all the types/other params etc. that participate in it. The compiler will guide you w/ errors  
3) Pull out all the functionality from the IResponseHandler into a ResponseHandler class - that server all - there you can add your Add etc. - and override for specific cases  
4) You'd need to cast to get to the 'handler' that can actually 'handle' - that (handler as ResponseHandler<TResponse>).Handle(response); 
Note
...that this is entirely futile if your 'handler' is only 'handling' (and that Add is the only method you really need) - i.e. this fully depends on your code and structure and the implementation of things. If your base interface 'serves the purpose' for something other than that - then it might be worth it. Otherwise - you can do all that with object pretty much - and cast from object and you won't be any less or more happier about it.