On Probability Measures on $\{-1,+1\}^n$ Let's put it formally...
Let $n$ be a positive integer and $E = \{-1,+1\}^n$.
Consider the set $\mathcal{P}$ of all the probability measures $\mu$ on $E$ such that
$$
\mu ( \pi_i^{-1} \{-1\} ) = \mu ( \pi_i^{-1} \{+1\} ) = \frac12 
$$
where $\pi_i : E \rightarrow \{-1,+1\}$ is the canonical projection onto the $i^\text{th}$ component of $E$, i.e. $\pi_i(x_1, \dots, x_n) = x_i$.
How can I parametrize $\mathcal{P}$?
Also, letting $\mathcal{C}$ be the set of all $n \times n$ correlation matrices, consider the map
$c: \mathcal{P} \rightarrow \mathcal{C} $ that assigns to each probability measure in $\mathcal{P}$ its correlation matrix.
Is $c$ injective? Surjective?
For the simple case $n=2$, it is clear to me that we can put $\mathcal{P}$ in a bijection with $[0,\frac12]$. For $a \in [0,\frac12]$, define $\mu$ as
$$
\mu \{-1,-1\} = \mu \{+1,+1\} = a \\
\mu \{-1,+1\} = \mu \{+1,-1\} = \frac12 - a 
$$
It's also clear that $c$ is bijective since the correlation is $4a-1$.
But what about the case of arbitrary $n$?
 A: The measures you are interested in are called symmetric Bernoulli distributions. The question which correlations are possible for such distributions is answered in the paper Admissible Bernoulli correlations.
To quote from the paper:

Consider a vertex of the n-dimensional cube $v\in\{0,1\}^n$. For
instance, when $n=5$, $v=(0,0,1,0,1)$ is such a vertex. Let 1 denote
the vector of all 1’s. Then for any $v\in\{0,1\}^n$, the distribution
$\text{Unif}(\{v,1−v\})$ (discrete uniform distribution over two
points: $v$ and $1−v$) has marginals that are all uniform over the
pair $\{0,1\}$. Hence all such distributions are multivariate
symmetric Bernoulli.
Any convex combination of multivariate symmetric Bernoulli
distributions will also be multivariate symmetric Bernoulli. Our main
result is that any admissible correlation structure can also be
realized as the correlation structure of such a convex combination.

They further characterize (in their Theorem 2) all possible correlations of symmetric Bernoulli distributions in terms of the $\text{CUT}_n$ polytope.
A: 
How can I parametrize $\mathcal{P}$?

This answer should help.
Taking the example ($n=3$), and given that here the marginals are uniform, hence $E[X_i]=0$, we have the parametrization
$$ P(x_1,x_2,x_3)=\frac{1}{2^3}\left( a_{123} x_1 x_2 x_3 +  
a_{12} x_1 x_2  + a_{23} x_2 x_3  + a_{13} x_1 x_3  + 
1
\right) $$
where $a_{i...k}=E[X_i ... X_k]$. In particular, here, $a_{i,j}=E[X_i X_j] = C_{i,j}$ for $i\ne j$.
(Obvioulsy $C_{i,i}=1$)
I think this answers your second question. Fixing the covariance matrix only fixes the second-order terms (just as fixing the marginals fixes the first order terms). This gives a one-to-one mapping only for the bivariate case. For $n>2$ there are additional terms, which correspond to additional degrees of freedom.
Hence, for a given covariance matrix there exist (in general) several (infinite) distributions.
