Schoenhardt polyhedron [(wikipedia)][1] 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).

  [1]: https://en.wikipedia.org/wiki/Sch%C3%B6nhardt_polyhedron