Truncated Hexahedron
This polyhedron can be made from just 2 different colors (as it is shown above) or with the 3 colors for the octahedral faces and one color for the triangular truncated faces. Each pair of truncated faces (octahedra) then would be in parallel planes.
To see the full-sized template click on this image: 
You will need to cut 6 of octagonal faces and 8 of the triangular faces.
You can assemble this polyhedron by attaching 3 octagonal faces to one of the triangle faces. The 8 edges of each octagonal face will be glued alternately to a triangle and then another octagonal face. All of the triangular faces will be surrounded by octagons.
To create this polyhedron with 4 colors, position each same-colored pair of octagonal faces on opposite sides of the cube.
