Aside from imposing a strong condition like "the rank of A is equal to the length of b" (which implies that Ax=b has a solution *for all* b), you have to check if b is in the subspace spanned by the columns of A (since Ax is a linear combination of the columns of A).

The easiest algorithmic way I can think of to do that is to perform column operations (multiplying columns by non-zero scalars and adding multiples of one column to another) to get a new set of vectors with the same span, but in "reduced column-echelon form" (i.e. with as many rows as possible consisting of a single non-zero entry). Then it is easy to read off what the coefficients of b would have to be if it were a linear combination of the columns, and you can just check if that linear combination works.