Theorem. Let $c(g)$ be the minimum number of cubes such that the boundary of some configuration of $c(g)$ cubes is a genus $g$ surface. Then $c(g)/g \to 2$ as $g \to \infty$.
Proof. We write $\chi(X)$ for the compactly supported Euler characteristic
of $X$, i.e.,
$\chi(X) = \sum (-1)^i \dim H^i_c(X, \mathbb{Q})$.
Note this is not a homotopy invariant: the compactly supported Euler characteristic of $\mathbb{R}^n$ is $(-1)^n$. It does however have the property that for reasonable finite disjoint union decompositions, $X = \coprod X_i$, we have $\chi(X) = \sum \chi(X_i)$.
Let $H_g$ be a closed genus $g$ handle-body. Then $$\chi(H_g) = 1-g.$$
On the other hand, let $K$ be a configuration of cubes. We write $K^0, K^1, K^2, K^3$ for the sets of vertices, edges, squares, and cubes, respectively,
and $k^0, k^1, k^2, k^3$ for their cardinalities. Then
$$\chi(K) = k^0 - k^1 + k^2 - k^3$$
We will count $k^0, k^1, k^2, k^3$ by looking at the interior of the $2 \times 2$ cube around each vertex. That is, abutting some vertex $v$, there is $1$ vertex, $6$ edges, $12$ faces, and $8$ cubes. More to the point, each $i$-dimensional face abuts $2^i$ vertices. We write $K_v$ to mean the configuration localized at $v$; we write $K^i_v$ for the set of $i$-dimensional faces which abut the vertex $v$, and $k^i_v$ for its cardinality. Thus:
$$\chi(K) = \sum_{v \in \mathbb{Z}^3} \sum_{i=0}^3 (-2)^{-i} \cdot
k^i_v $$
so we estimate
$$\frac{\chi(K)}{k^3} = \frac{\sum_{v \in \mathbb{Z}^3} \sum_{i=0}^3 (-2)^{-i} \cdot k^i_v }{\sum_{v \in \mathbb{Z}^3} 2^{-3} \cdot k^3_v } \ge
\min_{v \in \mathbb{Z}^3} \sum_i \frac{(-2)^{-i} \cdot k^i_v }{2^{-3} \cdot k^3_v }$$
The above inequality comes from the following fact: a (weighted) average is greater than the minimum term being averaged. Thus for any $a_i, b_i$ with $b_i > 0$, we have
$$\frac{\sum_i a_i}{\sum_i b_i} = \sum_i \frac{a_i}{b_i} \cdot \frac{b_i}{\sum b_i}
\ge \min_i \frac{a_i}{b_i}$$
Now let us analyze the possibilities for the right hand quantity
$$\tau(K_v) := \frac{8}{k_v^3} \cdot \left(k_v^0 - \frac{k_v^1}{2} + \frac{k_v^2}{4} -
\frac{k_v^3}{8} \right) $$
In fact, in the $2\times 2$ cube around a vertex, there are, up to symmetry, only 9 possible configurations of cubes whose boundary is (locally at that vertex) topologically a manifold: one each for every number of boxes other than 4, and for 4 boxes, the square, and the tripod configuration where, if say $v = (0,0,0)$, the cubes are the ones with most negative coordinates $(-1,-1,-1)$, $(-1, -1, 0)$, $(-1, 0, -1)$, and $(0, -1, -1)$. Note that the neighborhood of every point in the interior of a very porous solid is a tripod configuration.
It remains to compute in each of these cases the above quantity. For example, in the configuration $C_1$ when there is one cube, there is one vertex abutting the central one, three edges, three faces, and one cube. Thus this contributes
$$ \tau(C_1) = \frac{8}{1} \cdot \left(1 - \frac{3}{2} + \frac{3}{4} - \frac{1}{8} \right) = 1$$
We tabulate the remaining cases:
$$ \tau(C_2) = \frac{8}{2} \cdot \left(1 - \frac{4}{2} + \frac{5}{4} - \frac{2}{8} \right) = 0$$
$$ \tau(C_3) = \frac{8}{3} \cdot \left(1 - \frac{5}{2} + \frac{7}{4} - \frac{3}{8} \right) = -\frac{1}{3}$$
$$ \tau(C_4) = \frac{8}{4} \cdot \left(1 - \frac{5}{2} + \frac{8}{4} - \frac{4}{8} \right) = 0$$
$$ \tau(C_4') = \frac{8}{4} \cdot \left(1 - \frac{6}{2} + \frac{9}{4} - \frac{4}{8} \right) = -\frac{1}{2}$$
$$ \tau(C_5) = \frac{8}{5} \cdot \left(1 - \frac{6}{2} + \frac{10}{4} - \frac{5}{8} \right) = -\frac{1}{5}$$
$$ \tau(C_6) = \frac{8}{6} \cdot \left(1 - \frac{6}{2} + \frac{11}{4} - \frac{6}{8} \right) = 0$$
$$ \tau(C_7) = \frac{8}{7} \cdot \left(1 - \frac{6}{2} + \frac{12}{4} - \frac{7}{8} \right) = \frac{1}{7}$$
$$ \tau(C_8) = \frac{8}{8} \cdot \left(1 - \frac{6}{2} + \frac{12}{4} - \frac{8}{8} \right) = 0$$
Here, $C_4'$ is the tripod configuration. We conclude that
$$\frac{1-g(K)}{\# K^3} = \frac{\chi(K)}{\# K^3} \ge -\frac{1}{2}$$
hence $\# K^3 \ge 2g(K) - 2$.
On the other hand, for any family of configurations in which the fraction of $v$ with $K_v \sim C_4'$ -- i.e., the probability that (the neighborhood of a given cube is a very porous solid) -- tends to 1, the estimates above are sharp and $\# K^3 /g(K) \to 2$.
(An explicit calculation for the very porous cube appears in the comments above.) $\blacksquare$
