I know that shutdown() and awaitTermination() exist. The problem is that the runnables in the pool need to be able to add an unknown number (can't use a countdownlatch) of other runnables to it and if I call shutdown() those tasks will be rejected. How can I know when they're done?
Instead of submitting Runnable tasks to an Executor, you should rather use ForkJoinTask/ForkJoinPool instead. A ForkJoinTask runs inside a ForkJoinPool and can spawn an arbitrary number of (sub)tasks and wait for them to complete, without actually blocking the current thread. A ForkJoinTask is complete when all of its sub-tasks are done, so the entire computation is done, when the initial (root) ForkJoinTask is complete.
See Oracle - The Java™ Tutorials - Fork/Join for details.
As all of your tasks are resultless (Runnable), you should subclass RecursiveAction (which is itself a subclass of ForkJoinTask). Implement the method compute(), and spawn an arbitrary number of new tasks there by either calling invoke(subtask), invokeAll(subtask1, subtask2, ...) or subtask.fork() followed by subtask.join().
The entire computation is executed as follows:
MyRecursiveAction task = new MyRecursiveAction(params);
ForkJoinPool pool = new ForkJoinPool(numberOfThreads);
pool.invoke(task); // will block until task is done
Unfortunatley the advantages of Fork/Join have some limitations, e.g.:
(...) Computations should ideally avoid synchronized methods or blocks, and should minimize other blocking synchronization apart from joining other tasks or using synchronizers such as Phasers that are advertised to cooperate with fork/join scheduling. Subdividable tasks should also not perform blocking I/O, and should ideally access variables that are completely independent of those accessed by other running tasks. These guidelines are loosely enforced by not permitting checked exceptions such as IOExceptions to be thrown. (...)
For more detail see API docs of ForkJoinTask.