Your question is quite underspecified, and so difficult to answer.  Let me narrow it considerably,
perhaps well beneath your interests, to convex polyhedra.  Then you can use this result:
The convex combination of convex sets is itself convex.
<hr>
Here is an (entirely skippable) proof.
Let $A$ and $B$ be two convex sets, and $C= \alpha A + \beta B$ a convex combination,
with $\alpha,\beta \ge 0$, $\alpha+\beta=1$.
Take two points in $C$:
$$
c_i = \alpha a_i + \beta b_i
$$
$i=1,2$.
Now consider any convex combination of $c_1$ and $c_2$
(with the usual restrictions of the coefficients $\gamma$ &amp; $\delta$):
$$
\gamma c_1 + \delta c_2 = \gamma \alpha a_1 + \gamma \beta b_1 + \delta \alpha a_2 + \beta \delta $$
$$= \alpha ( \gamma a_1 + \delta a_2) + \beta ( \gamma b_1 + \delta b_2 ) $$
$$= \alpha a_3 + \beta b_3$$
So this is in $C$; so $C$ is convex.
<hr>
So, let your $n$ convex polyhedra be $P_1,\ldots,P_n$.  Then define their average as
$(P_1 + \cdots + P_n) / n$.  This will be a convex polyhedron.

But probably you are interested in nonconvex polyhedra?  You might be able to proceed
by partitioning your nonconvex polyhedron into convex polyhedra, an interesting
challenge in its own right (see the 2D equivalent discussed on MO here:
"[Partitioning a polygon into convex parts][1]"). 

And as Douglas' question indicated, you might be clearer on whether all your polyhedra
have the same genus.



  [1]: http://mathoverflow.net/questions/60212/