I've seen this done in Blender. I don't know how to do it exactly, but I've watched a video tutorial. It involves marking edges as "seams" and then using the "LSCM Unwrap" feature built into blender. By marking seams, you are telling it exactly what you described above, i.e. where to "cut" the mesh before attempting to unwrap it. Then the "LSCM Unwrap" attempts to heuristically unwrap the mesh in such a way as to maximize the coverage on the texture map, while minimizing the distortion of angles in the unwrapped mesh. If you haven't heard of it, blender is a powerful and fast open-source 3d modeling program. It takes a while to learn it. It has about a bazillion tricky functions - and folks who know blender really well invoke them all with hot keys. If there is some easier tool, by all means, don't start learning blender just for this. But if all else fails, give it a try. At least it's free!

---

Renderosity forum reply notifications are wonky. If I read a follow-up in a thread, but I don't myself reply, then notifications no longer happen AT ALL on that thread. So if I seem to be ignoring a question, that's why. (Updated September 23, 2019)