How can I delete internal vertices/faces and edges?
I think booleans are the answer, but you can do this without separating parts of the object. As of Blender 2.77 you can use the Intersect option in edit mode.

Here I have two overlapping cubes:



Select one of the parts (as shown above) and choose Mesh> Faces> Intersect (Boolean) from the 3D header.

From the toolbar (T) change the boolean type to 'Union':



The two meshes have now been 'merged' with their overlapping geometry removed:



You can either do this once for each piece of intersecting geometry or select all the intersecting pieces (apart from the piece they are intersecting with) and boolean them all at once.