- you create an interface in your code, say com.foo.MyInterface;
 - you create implementations of this interface;
 - you create a file in META-INF/services, named after your interface (therefore, in this example, META-INF/services/com.foo.MyInterface;
 - in this file, you add implementations of your interfaces, one per line.
 
The ideal solution is to generate them at compile time/packaging time. But you then stumble upon another problem: your IDE may not generate them; crashes again!
As to build systems, Maven has a plugin available; but for Gradle, nothing... So, I had to "write" it. I took the aforementioned plugin as a reference and came up with the below code, which generates a task called generateServiceFiles.
Now, beware that this code reflects my Groovy/Gradle experience: not even a week! Seasoned Groovy developers in particular will certainly balk at the number of semicolons ;) But it works... Feel free to pick it up and make a plugin out of it!
/*
 * List to fill with your interfaces to be implemented
 */
project.ext {
    serviceClasses = [
        "com.foo.MyInterface",
        "org.bar.OtherInterface"
    ];
};
project.ext {
    dotClass = ".class";
    classpathURI = sourceSets.main.output.classesDir.canonicalFile.toURI();
    serviceMap = new HashMap<Class<?>, List<String>>();
    tree = fileTree(classpathURI.path)
        .filter({ it.isFile() && it.name.endsWith(dotClass); }); // FileTree
    resourceURI = sourceSets.main.output.resourcesDir.canonicalFile.toURI()
        .resolve("META-INF/services/"); // Ending '/' is critical!
}
task generateServiceFiles(dependsOn: compileJava) << {
    if (!project.hasProperty("serviceClasses"))
        return;
    if (serviceClasses.empty)
        return;
    project.ext({
        runtimeURLs = sourceSets.main.runtimeClasspath.collect({
            it.toURI().toURL()
        }) as URL[];
        classLoader = URLClassLoader.newInstance(runtimeURLs);
    });
    serviceClasses.each() {
        serviceMap.put(classLoader.loadClass(it), new ArrayList<String>());
    };
    tree.each() {
        File candidate ->
            serviceMap.each() {
                key, value ->
                    final String className = toClassName(candidate);
                    if (isImplementationOf(key, className))
                        value.add(className);
            }
    };
    createServicesDirectory();
    serviceMap.each() {
        name, list ->
            if (list.empty)
                return;
            final String path = resourceURI.resolve(name.canonicalName)
                .getPath();
            new File(path).withWriter {
                out -> list.each() { out.writeLine(it); }
            };
    };
}
processResources {
    dependsOn(generateServiceFiles);
}
/*
 * Support methods for the generateServiceFiles task
 */
void createServicesDirectory()
{
    final File file = new File(resourceURI.getPath());
    if (file.exists()) {
        if (!file.directory)
            throw new IOException("file " + file + " exists but is not a directory");
        return;
    }
    if (!file.mkdirs())
        throw new IOException("failed to create META-INF/services directory");
}
String toClassName(final File file)
{
    final URI uri = file.canonicalFile.toURI();
    final String path = classpathURI.relativize(uri).getPath();
    return path.substring(0, path.length() - dotClass.length())
        .replace("/", ".");
}
boolean isImplementationOf(final Class<?> baseClass, final String className)
{
    final Class<?> c = classLoader.loadClass(className);
    final int modifiers = c.modifiers;
    if (c.anonymousClass)
        return false;
    if (c.interface)
        return false;
    if (c.enum)
        return false;
    if (Modifier.isAbstract(modifiers))
        return false;
    return Modifier.isPublic(modifiers) && baseClass.isAssignableFrom(c);
}