How can this system be solved without using linear programming?
Your problem is the linear feasibility problem in the standard form, with an extra condition that the constraint matrix is sparse. Now note:
(1) It is well-known that linear programming is equivalent to the linear feasibility problem in the standard form.
(2) You can easily convert a linear feasibility problem in the standard form to one with the extra condition that each row of the constraint matrix has at most three nonzero elements. For example, decompose w−x+y−z=b into w+y−t=0 and t−x−z=b, where t is a fresh nonnegative variable. (The detail is left as an exercise.)
These together mean that an algorithm for your problem can be used to solve the linear programming. Equivalently, you cannot hope for an essentially simpler algorithm for your problem than an algorithm for linear programming.