How to find all matrices $X \in \{0,1\}^{n \times m}$ that satisfy these equations?
$$X X^t = A \\ \sum_{j=1}^m x_{ij} = 2$$
These articles maybe could help us:
Solving X times Transpose of X Is Equal to A - Over Integers (in which he claims to find all $X$ to satisfies, but in Integers, maybe we can transform this solution to this problem and find the solutions).
For general $A,X~$ this is a very difficult problem, but the condition you give that the rows of $X~$ have sum 2 makes it much easier. Consider each row to be an edge of a graph $G~$ (i.e. the two ones in the row say which two vertices are connected). Then $A~$ is the adjacency matrix of the linegraph $L(G)$, except for the diagonal. It has long been known that one can determine $G~$ from $L(G)~$ even in linear time. See this article of Lehot, for example.
(ADDED:) The theory of linegraphs says that two connected simple graphs have isomorphic linegraphs iff they are isomorphic or one is $K_{1,3}$ and the other is $K_3$. For disconnected simple graphs, you can swap any $K_{1,3}$ component with $K_3$ and vice-versa, and you can also add isolated vertices (which doesn't change the linegraph).
So to find all the solutions for $X$:
Off-diagonal entries in $A$ equal to 2 correspond to equal rows of $X$. Collapse all sets of equal rows into single rows so that the problem reduces to one where $A$ is 0-1 off the diagonal.
Find the connected components of $A$ and solve the inverse linegraph problem for them. If the inverse linegraph problem has multiple solutions (as above), take all solutions. (If you are told in advance how many columns $X$ must have, there will be few possibilities with the right total number of vertices.)
Now apply all possible permutations of the columns (if you really want all solutions).
