NURBS surface from branching curves?
Blender is not known or marketed for its NURBS support, it is primarily a polygon modelling tool. While we have great modifiers like the Skin Modifier you mentioned, we don't have anything out of the box that would produce comparable NURBS surfaces.

A scripted solution also seems a bit beyond what is convenient to do in Blender, the API has limited support for generating arbitrary patch shapes that would be needed to do your Question justice.

I'd like to be proven wrong someday, or today, but for now I'd like to offer this as an interim answer and not just a cheeky comment. There are better tools for generating NURBS, consider freeCAD or any of the other free CAD/NURBS alternatives.