Yes, this is true.

One strategy is to use the naïve approach of counting degrees of freedom and constraints. For triangulated polyhedra one can easily show with the Euler characteristic that the expected dimension (number of variables minus number of equations) of the realization space modulo Euclidean isometries is zero, and Cauchy would then imply that this is the case for a convex embedding. Then we can get to any polyhedron with a nontriangular face by removing some number of edges from a triangulated one and thus the dimension of the realization space is positive. However, this alone doesn't guarantee that the set of *real* points is positive dimensional. This point is made in Pak's lectures, e.g. Remark 26.3 and footnote 55 on page 248.

To deal with this issue, we appeal to a theorem of Asimow and Roth (Section 3 of "The rigidity of graphs", L. Asimow and B. Roth, Trans. Amer. Math. Soc. 245 (1978), 279-289).

This theorem states: Let $G$ be a graph with $v$ vertices, $e$ edges and let $p\in\mathbb{R}^{nv}$ be a regular point of the length-squared function $f_G:\mathbb{R}^{nv}\rightarrow \mathbb{R}^e$ (which maps a point in $\mathbb{R}^{nv}$, to the vector of squared-edge lengths). Suppose that the affine span of $p$ viewed as a configuration of $v$ points in $\mathbb{R}^n$ is all of $\mathbb{R}^n$. Then $(G,p)$ is (locally) rigid (every $q$ sufficiently close to $p$ with $f_G(q)=f_G(p)$ is induced by an isometry of $\mathbb{R}^n$) if and only if the rank of $df_G(p)=nv-n(n+1)/2$.

Now let $P'$ be a triangulation of your polyhedron $P$ and let $E'$ be the 1-skeleton of $P'$. Suppose that $E$ (and hence $E'$) both have $v$ vertices with placement $p\in\mathbb{R}^{3v}$. Since $E'$ is the graph of a triangulated polyhedron, $E'$ has $e'=3v-6$ edges and by assumption $E$ has $e<3v-6$ edges. Cauchy's rigidity theorem guarantees that $E'$ is rigid, hence the rank of $df_{E'}(p)=3v-6=e'$. Note that the matrix for $df_{E}(p)$ consists of a strict subset of rows of $df_{E'}(p)$ and so by basic linear algebra its rank is $e<3v-6$. Asimow-Roth thus implies that $(E,p)$ cannot be rigid.

Ivan Izmestiev has pointed out the following doesn't work: see the comments.

~~This follows from Theorem 30.1 (section 30.9, page 283) in Igor Pak's lecture notes, which is proved in section 37.3 (page 332). To see this, consider any triangulation $P'$ of $P$. Then let $F_1,F_2$ be a pair of adjacent triangles in $P'$ which are part of a triangulation of a non-triangular face of $P$. Theorem 30.1 implies that $P''=P'\setminus (F_1\cup F_2)$ is a flexible polyhedral surface, and the flexes of $P''$ give rise to a desired flex of $E$, the 1-skeleton of $P$.~~

~~
~~~~The proof relies on the Alexandrov existence theorem, which states that "every intrinsically convex 2-dimensional surface homeomorphic to a sphere is isometric to the surface of a convex polytope in $\mathbb{R}^3$ or a doubly covered polygon".~~