I have given some detail in a comment to another answer. I have a proof that the number of determinants is greater than 4 times the nth Fibonacci number for (n+1)x(n+1) (0,1) matrices, and I conjecture that for large n the number of distinct determinants approaches a constant times n^(n/2). Math Overflow has some hints of the proof in answers I made on other questions.
I am interested in your idea for an application, and am willing to share more information on this subject.
Gerhard "Ask Me About System Design" Paseman, 2010.03.19
I can show that there is no universal formula. More precisely, let $k$ be an algebraically closed field and let $R = k[w,x,y,z,\Delta]/(\Delta^2-wz+xy)$. I claim that there do not exist $2 \times 2$ matrices $A_1$, $A_2$, ..., $A_{2t}$ with entries in $R$, such that every matrix occurs an even number of times in the list up to transpose, and $\left( \begin{smallmatrix} w & x \\ y & z \end{smallmatrix} \right) = A_1 A_2 \cdots A_{2t}$. In fact, we are going to show something much stronger: It is impossible to write $\left( \begin{smallmatrix} w & x \\ y & z \end{smallmatrix} \right)$ as $MN$ for two noninvertible $2 \times 2$ matrices with entries in $R$.
Since $R$ is a graded integral domain, $\det M$ and $\det N$ would have to be of pure degree. If $\det M$ has degree $0$ then $M$ is invertible. So we must have $\det M$ and $\det N$ of degree $1$.
Write $M=M_0 + M_1 + \cdots$ where $M_k$ is pure of degree $k$, and likewise for $N$. So $$\left( \begin{smallmatrix} w & x \\ y & z \end{smallmatrix} \right) = M_0 N_1 + M_1 N_0.$$
Since $\det M$ has no constant term, we have $\det M_0 =0$ and, similarly, $\det N_0 =0$. Let $\left( \begin{smallmatrix} u_1 & u_2 \end{smallmatrix} \right) \in k^2$ be in the left kernel of $M_0$ and let $\left( \begin{smallmatrix} v_1 \\ v_2 \end{smallmatrix} \right) \in k^2$ be in the right kernel of $N_0$. So the above equation shows that $\left( \begin{smallmatrix} u_1 & u_2 \end{smallmatrix} \right) \left( \begin{smallmatrix} w & x \\ y & z \end{smallmatrix} \right) \left( \begin{smallmatrix} v_1 \\ v_2 \end{smallmatrix} \right) =0$.
But there are no nonzero vectors in $k^2$ for which $\left( \begin{smallmatrix} u_1 & u_2 \end{smallmatrix} \right) \left( \begin{smallmatrix} w & x \\ y & z \end{smallmatrix} \right) \left( \begin{smallmatrix} v_1 \\ v_2 \end{smallmatrix} \right) =0$, a contradiction.
UPDATE: Pushing this argument further, I can show that $\begin{pmatrix} 0 & u & v & w \\ -u & 0 & x & y \\ -v & -x & 0 & z \\ -w & -y & -z & 0 \end{pmatrix}$ cannot be expressed as $MN$ with $\det M$ and $\det N$ nonconstant. Proof: Abbreviate the above matrix to $S$. As before, deduce that we can write $M_0 N_0 =0$ and $M_0 N_1 + M_1 N_0 = S$ with $\det M_0 = \det N_0 = 0$. So $\mathrm{rank} M_0 + \mathrm{rank} N_0 \leq 4$. Without loss of generality, suppose that $M_0$ has nullity at least $2$ and $N_0$ has nullity at least $1$. So, as before, we can find linearly independent constant vectors $p$ and $q$ with $p^T M_0=q^T M_0 =0$ and a nonzero vector $r$ with $N_0 r=0$. We have $p^T S r = q^T S r = 0$ as before.
Let $p=(p_1, p_2, p_3, p_4)$ and $r=(r_1, r_2, r_3, r_4)$. Looking at the coefficient of $u$ in $p^T S r$, we get $p_1 r_2 = p_2 r_1$. Looking at $v$, $w$, $x$, $y$ and $z$, we see that $p_i r_ = p_j r_i$ for all $(i,j)$, so $p$ and $r$ are proportional. Similarly, $q$ and $r$ are proportional, so $p$ and $q$ are proportional, contradicting that we choose them linearly independent. QED.
I have no $2 \times 2$ counter-example.
Best Answer
By "corresponding submatrices" I presume you mean those $2\times2$ minors obtained by deleting $n-2$ colums and $n-2$ rows, where these columns and rows have the same $n-2$ indices. Once you've calculated the determinants of these submatrices you recover the action of $A$ on the exterior square $\Lambda^2 V$.
Now the following paper: "An algorithm for recognising the exterior square of a matrix" by Catherine Greenhill explains how to then obtain the original matrix $A$. Here's the relevant quote:
The paper can be downloaded here.
One needs to be slightly careful here, because the exterior square does not quite determine the matrix $X$ uniquely. Here is another quote from the paper:
So if the rank is at least three (which it is, since you are assuming invertibility), then we are pretty much done. I'm guessing that the situation where the rank is $\leq 2$ would be easy enough to resolve but in any case that's outside the scope of the question...