First, note that there is a terminology issue which may prove troublesome when navigating the literature: generally, a "triangulation" (as well as the weaker notion of "tiling") is required to not add vertices. If we adopt this meaning, then there are non-triangulable polyhedra; this was first shown by Lennes, and Braxton Carrigan's thesis seems a good expository source.
However, you don't appear to mind additional vertices. When we drop that requirement, and calling the resulting property "decomposability," it turns out that every polyhedron is decomposable. This is mentioned frequently in the computational geometry literature, e.g. in the beginning of this paper; however, that literature is (understandably!) more interested in "efficient" decompositions rather than the mere existence of decompositions, and I haven't yet found a source for this weaker fact.
(Actually, the linked paper only talks about decompositions into convex polyhedra. But this is enough, since every convex polyhedron is decomposable (indeed, *triangulable): first triangulate each face as usual. Now pick a vertex $v$ and connect each other vertex to $v$. Every triangle in a face of the polyhedron now generates a tetrahedron (or contains $v$, in which case ignore it) - given by its three vertices together with the vertex $v$ - and these tetrahedra give a triangulation of the whole polyhedron. So it's enough to show just that arbitrary polyhedra can be decomposed into convex polyhedra.)