Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed
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".
Let me show how to reduce the problem to Alexandrov existence theorem; that is, the original idea of j.c. works.
Let us modify the polyhedron by adding a low pyramid over each non-triangular face. The edges which we add this way will be called new.
This graph is rigid by Cauchy theorem. Moreover if we slightly change the length of a new edge, then by Alexandrov existence we get one parameter family of rigid graphs.
Evidently the old part of graph moves, hence we get the required deformation.
I am not seeing the nontrivial deformation of the $E$ below, a triangulation of a cube except for the top face. Can someone explain? Thanks!
Update. The deformation of this cardboard model is essentially what Nik Weaver described in a comment.
