Forking + threads is very messy, but it's not quite that pathological. I'd like to see an interface similar to posix_spawn() become the norm for spawning processes, with a fallback to fork()+exec() for more difficult use cases, but I don't think posix_spawn() is good enough.
Edit: upon re-reading the man page, this bit caught my eye:
"If you need to use these frameworks in the child process, you must exec. In this situation it is reasonable to exec yourself."
So that would be one (highly painful) way to handle this safely. Fork, then self-exec, passing in arguments that tell the newly execed process what you really want to run. The new process can then do the /dev/fd listing in peace, then call exec again. Eww.
Another silly way to do things is to have the parent process send a list of fds to close over a pipe, which at least doesn't require a second call to exec().
I think the problem with close-on-exec is always going to be simple though: you have to make sure every library you use sets the flag.
I suppose if I am not mistaken you could go the pre-readdir() route and open a directory with open() and read it with read(). Probably a portability mess though.
(In both cases, you can't count on currently acquired locks ever being released. In a signal handler, this is because it could be acquired on the current thread, and post-fork, this is because all other threads have been killed from the perspective of the child process. As such, no lock-based code can safely be called.)