Subdividing a mesh into convex subvolumes and tagging faces
1a.  The technique you are looking for is called Convex Decomposition and there is a fair amount of research on it.  It's good for skeletonizing meshes for rigging, and I'm sure many other useful things.

http://masc.cs.gmu.edu/wiki/ACD

1b.  I do not believe there is any way to do this automatically in blender natively.

1c.  There is an addon to do this volume decomposition in blender, it relies on external code library and is more targetdd at the game engine however you may be able to tailor it's results to your needs.  This is an approximate decomposition.
http://blenderartists.org/forum/showthread.php?357513-Volumetric-Hierarchical-Approximate-Convex-Decomposition-%28e-g-for-BGE-Physics%29

2a. If your method is actually going to create interior geometry in the same mesh, then finding the non manifold edges and then interior faces is not a big deal. However my answer above is going to create approximate new objects

2b.  If you are able to split your mesh into groups of verts, using the bmesh convex hull modifier will tell you what new geomtry it creates.  By the definitition of your problem, all the new geometry will be the