Both the cell complex, $C$, and the dual cell complex $C'$ are refined by the first barycentric subdivision $BC$. There are maps $C \to BC$ and $C' \to BC$, sending a cell $\sigma$ to the sum of all cells of the same dimension contained in $\sigma$; these maps are both quasi-isomorphisms.
So, if you allow me to formally invert quasi-isomorphisms, I'm done.
Is the question whether there is an honest map of chain complexes between $C$ and $C'$, without subdividing?
UPDATE Here is something you can do, and something you can't do.
With $C$ and $BC$ as above, and $r : C \to BC$ the refinement map, there is a homotopy inverse $s: BC \to C$. (More precisely, $C \to BC \to C$ is the identity, and $BC \to C \to BC$ is homotopic to the identity.) Working the same trick with $r' : C' \to BC$, we get quasi-isomorphisms between $C$ and $C'$ which are homotopy inverse to each other. As you will see, however, this construction is very nongeometric and inelegant.
Construction: Let $q:BC \to Q$ be the cokernel of $C \to BC$. An easy computation checks that each $Q_i$ is free. Since $C \to BC$ is a quasi-isomorphism, $Q$ is exact. An exact complex of free $\mathbb{Z}$ modules must be isomorphic to a direct sum of complexes of the form $\cdots \to 0 \to \mathbb{Z} \to \mathbb{Z} \to 0 \to \cdots$. Choose such a decomposition of $Q$, so $Q_i = A_{i+1} \oplus A_{i}$ and the map $Q_i \to Q_{i-1}$ is the projection onto $A_{i}$.
Now, consider the map $q_i^{-1}(A_i) \to A_i$ in degree $i$. This is surjective, and $A_i$ is free, so choose a section $p^1_i$. We also define a map $p^2_i$ from the $A_{i+1}$ summand of $Q_{i}$ to $BC_i$ by $p^2_i = d p^1_{i+1} d^{-1}$. In this way, we get maps $p_i = p^1_i \oplus p^2_i: Q_{i} \to BC_i$ which give a map of chain complexes.
We note that $qp: Q \to Q$ is the identity. Therefore, $1-pq$, a map from $BC \to BC$, lands in the subcomplex $C$ and gives a section $s:BC \to C$. Proof of the claim about homotopies will be provided on request.
On the other hand, here is something you can't do: Get the quasi-isomorphism to respect the symmetries of your original space. For example, let $C$ be the chain complex of the cube, and $C'$ the chain complex of the octahedron. I claim that there is no quasi-isomorphism $C \to C'$ which commutes with the group $S_4$ of orientation preserving symmetries.
Consider what would happen in degree $0$. A vertex of the cube must be sent to some linear combination of the vertices of the octahedron. By symmetry, it must be set to
$$a (\mbox{sum of the "near" vertices}) + b (\mbox{sum of the "far" vertices})$$
for some integers $a$ and $b$. But then the map on $H_0$ is multiplication by $3(a+b)$, and cannot be $1$.
I imagine you want something stronger then my first answer, but weaker than my second. I am not sure what it it, though.
UPDATE This version is substantially improved from the one posted at 8 AM.
I now think I can achieve $\mathbb{Z}/p$ using $O( \log p)$ vertices. I'm not trying to optimize constants at this time.
Let $B$ be a simplicial complex on the vertices $a$, $b$, $c$, $a'$, $b'$, $c'$ and $z_1$, $z_2$, ..., $z_{k-3}$, containing the edges $(a,b)$, $(b,c)$, $(c,a)$, $(a',b')$, $(b',c')$ and $(c',a')$ and such that $H^1(B) \cong \mathbb{Z}$ with generator $(a,b)+(b,c)+(c,a)$ and relation
$$2 {\large (} (a,b)+(b,c)+(c,a) {\large )} \equiv (a',b') + (b',c') + (c',a').$$
I think I can do this with $k=6$ by taking damiano's construction with $p=2$ and adding three simplices to make the hexagon $(h_1, h_2, \ldots, h_6)$ homologous to the triangle $(h_1, h_3, h_5)$.
Let $B^n$ be a simplicial complex with $3+nk$ vertices $a^i$, $b^i$, $c^i$, with $0 \leq i \leq n$, and $z^i_j$ with $0 \leq i \leq n-1$ and $1 \leq j \leq k-3$. Namely, we build $n$ copies of $B$, the $r$-th copy on the vertices $a^r$, $b^r$, $c^r$, $a^{r+1}$, $b^{r+1}$, $c^{r+1}$ and $z^r_1$, $z^r_2$, ..., $z^r_{k-3}$. Let $\gamma_i$ be the cycle $(a^i,b^i) + (b^i, c^i) + (c^i, a^i)$.
Then $H^1(B^n) = \mathbb{Z}$ with generator $\gamma_0$ and relations
$$\gamma_n \equiv 2 \gamma_{n-1} \equiv \cdots \equiv 2^n \gamma_0$$
Let $p = 2^{n_1} + 2^{n_2} + \cdots + 2^{n_s}$.
Glue in an oriented surface $\Sigma$ with boundary $\gamma_{n_1} \sqcup \gamma_{n_2} \sqcup \cdots \sqcup \gamma_{n_s}$, genus $0$, and no internal vertices.
In the resulting space, $\sum \gamma_{n_i} \equiv 0$ so $p \gamma_0 \equiv 0$, and no smaller multiple of $\gamma_0$ is zero. We have use $3 + k \log_2 p$ vertices. This is the same order of magnitude as Gabber's bound.
Best Answer
Given any graph $G$, let $G'$ denote $G$ with a new vertex $v$ adjacent to every vertex of $G$. The clique complex of $G'$ is contractible, while the independence complex of $G$ and $G'$ are the same except for an isolated vertex. Similarly we can adjoin a new isolated vertex $w$ to $G$, obtaining a graph $G''$ with a contractible independence complex but with the same clique complex as $G$ except for an isolated vertex. Thus in general there is not much connection between the topologies of the clique and independence complexes.