The way the Alexandrov phrases the theorem, in his book Convex Polyhedra (p.421) is:
Theorem. A closed convex polyhedron with infinitesimally rigid faces is infinitesimally rigid.
When the polyhedron is simplicial, i.e., all faces are triangles, then all faces are infinitesimally rigid. The 1-skeleton of a cube is not rigid, because the squares can deform to rhombi. But if the cube faces are rigid squares, then this nonsimplicial polyhedron is rigid. So it depends on what you consider a polyhedron—Is it built out of sticks or out of plates?
I am not sure what is meant by a non-«strictly convex polyhedron». [Igor clarifies below.]