Concatenating polyhedra at their region of contact
I was recently referred to an article 'Mesh arrangements for solid geometry' by Qingnan Zhou et. al. [pdf]
and the corresponding code by Dr. Campen which exactly solves this problem. 

This algorithm inserts new vertices and edges in the region of intersection between $P1$ and $P2$ thereby a generating new polyhedron $P$ and evaluates boolean operators on $P$ by selecting/rejecting vertices and edges depending on the operator. For my problem, $P$ forms the solution.

However, out of curiosity I would like to know if anyone has an alternative to this approach.

Update: I have tested the tool referred above against my original problem, it successfully prevents self-intersection by inserting new vertices and edges at the region of contact between $P1$ and $P2$.