Decoupling a Factory to allow for Custom Factory Implementations

I'm currently working on a library and I've tried to abstract parts of the code through the use of interfaces as much as possible. However some areas need to return concretions, as I can see no other way of returning the data in a clean way. For example, One area of code needs to return a key object:

public IKey GenerateKey() {
    return new Key(param1, param2, param3);
}

My solution to this currently is to create a Factory class with static methods for returning concretions:

public IKey GenerateKey() {
    return KeyFactory.Get(param1, param2, param3);
}

But now I feel like I have high coupling between the factory and the codebase, as there's a few lines in many parts that request objects from the factory. It also just feels lazy, as I can whip up some factory function to give me a concrete class in many situations.

My biggest problem is in allowing people to replace classes by creating their own classes implementing current interfaces. I need to allow users to create their OWN factories for their OWN class implementations. If I make an interface for my factory, and allow users to create their own factory implementing the interface, then I need a higher-up factory to create THAT factory, and so on...

I need users to be able to create their own custom classes implementing the correct interfaces, create their own factory that can return their custom class by other areas of the code where needed, and it all to work seamlessly together.

Edit: This is the idea I have currently, however injecting the factory seems like an unconventional thing to do when using a library in Java.

public class Key implements IKey {
    public Key(param1) {
        //do something
    }
    //other methods
}

public interface IKey{
    //Other methods
}

public class RicksFactory {
    public IKey getKey(param1) {
        return new Key(param1);
    }
}

public interface IFactory {
    IKey getKey(param1);
}

//This class is a singleton, for other classes in
//library to find it without having to do dependency
//injection down all the levels of classes.
public class TopClassInLibrary {
    //Singleton init

    public void SetFactory(IFactory factory) {
        this.factory = factory;
    }

    public IFactory GetFactory() {
        return new RicksFactory();
    }
}

public class Main {
    public static void main(String[] args) {
        TopClassInLibrary.GetInstance().SetFactory(new RicksFactory());

    }
}