Schoenhardt polyhedron (wikipedia) is a star-shaped polyhedron in $\mathbb{R}^3$ with triangular faces that cannot be triangulated without subdividing its faces. So the answer is no even without requiring the regularity of the subdivision.

Schoenhardt polyhedron (wikipedia) is a star-shaped polyhedron in $\mathbb{R}^3$ with triangular faces that cannot be triangulated without subdividing its faces. So the answer is no even without requiring the regularity of the subdivision.

EDIT: As the OP remarks in the comment, this does not answer the question because vertices in the interior are permitted (and then every star-shaped polyhedron has a triangulation, by starring the boundary from a point which sees the whole boundary).