All vertices can always be connected.

Your restrictions sound more like :

- every vertex is connected to at least 3 edges.
- every edge must be shared by 2 and only 2 triangles.
- every edge must not intersect any of the triangles.

So a brute-force way would be to generate random points, connected by random edges to form triangles, then clean up every conflicting vertex and edge. Of course a lot of junk will be thrown out.

You may have other constraints, like all no disjoints parts, or no donut-holes, etc. So maybe a less brute force approach would be to go from a cube, and catmull-clark subdivide it with random noise, each iteration with a smaller magnitude.