Even though it is NP-complete, you can do a lot better than searching through all $2^n$ possibilities.  In practice, you might try a [SAT solver][1], with the clauses
$\bigvee_{j: A_{ij} = 1} x_j$ for each row $i$ and $\overline{x_j} \vee \overline{x_k}$ for each pair $(j,k)$ such that for some row $i$, $A_{ij} = 1$ and $A_{ik} = 1$.  
This can sometimes solve a problem with hundreds of clauses and variables
in a reasonable time.

Counting or estimating the number of solutions (in a case where that number is not $0$)
might be more difficult.

  [1]: http://en.wikipedia.org/wiki/SAT_solver#Algorithms_for_solving_SAT