I am aware that $S_4\times Z_2$ is the full symmetry group of the octahedron and the cube (since they are duals). I've found a relatively straightforward way to generate this group with $3$ elements, but I don't know how to prove it cannot be done with $2$. I have proved that $S_4$ needs to be generated with at least $2$ elements.
I thought $Z_2\times Z_2$ might be a quotient of $S_4$, but it is not.
$S_4\times S_2$ can be generated by two elements in many ways. For example, let $S_4$ act on $\{1,2,3,4\}$ and $S_2$ on $\{5,6\}$ and let $g=(1,2,3,4)$ and $h=(1,2,3)(5,6)$. Now, $h^3=(5,6)$ and $h^2=(3,2,1)$.
Note that $h^2$ and $g$ are both contained in $S_4$. They generate subgroups of order $3$ and $4$ (which intersect trivially by Lagrange), so they generate a group of order at least $12$. Since $g$ is not in $A_4$, this must be the whole $S_4$. Now, throw in $h^3$ and you get $S_4\times S_2$.