This should be a more concise way of setting up the problem.
mat = Table[m[i, j], {i, 1, 4}, {j, 1, 4}];
{eigs, vecs} = Eigensystem[mat];
c1 = Thread[vecs[[4, All]] >= 0];
c2 = Flatten[{eigs[[4]] == 0, Thread[Most[eigs] <= 0]}];
c3 = Thread[Flatten[mat] >= 0];
vars = Flatten[mat];
constraints = Join[c1, c2, c3]
So if I understand correctly you are seeking a matrix with all nonnegative entries such that three eigenvalues are nonpositive, one is zero, and a normalization of sorts is imposed wherein all fourth components of eigenvectors are nonnegative. (Or something got transposed and the intent was that the null vector have all nonnegative components). Assuming I have this much correct, the normalization can be dropped because it can be enforced after the fact, multiplying eigenvectors by -1 where needed. So I redo the constraints like so.
constraints = Join[(*c1,*)c2, c3];
This causes FindInstance to go a much faster route it seems. It finds the "obvious" solution.
Timing[inst = FindInstance[constraints, vars]]
(* Out[62]= {0.00738, {{m[1, 1] -> 0, m[1, 2] -> 0, m[1, 3] -> 0,
m[1, 4] -> 0, m[2, 1] -> 0, m[2, 2] -> 0, m[2, 3] -> 0,
m[2, 4] -> 0, m[3, 1] -> 0, m[3, 2] -> 0, m[3, 3] -> 0,
m[3, 4] -> 0, m[4, 1] -> 0, m[4, 2] -> 0, m[4, 3] -> 0,
m[4, 4] -> 0}}} *)
Requesting more solutions will hang it though.
Here is a different formulation. It might not perform any better but it does remove the Root objects from consideration, by setting up explicit vectors for the eigenvectors.
mat = Array[m, {4, 4}];
eigs = Array[e, 4];
vecs = Array[v, {4, 4}];
tvecs = Transpose[vecs];
eqns = Table[
Thread[mat . vecs[[j]] == eigs[[j]]*tvecs[[j]]], {j, 4}];
c2 = Flatten[{eigs[[4]] == 0, Thread[Most[eigs] <= 0]}];
c3 = Thread[Flatten[mat] >= 0];
vars = Flatten[{mat, eigs, vecs}];
constraints = Flatten[{eqns, c2, c3}];
Again it is fast to find the trivial solution. I do not know if FindInstance or Reduce will go beyond that though.
