Feasible solution existence
Theory

There's a simple argument to show you can't help to do that much better.  In particular, testing for feasibility of a set of linear inequalities can't be too much easier than optimizing a linear objective function subject to a set of linear inequalities.

Why?  If we want to optimize the objective function $\Psi$ subject to a set $\mathcal{S}$ of inequalities, one way to do that is to use binary search on the value of the objective function.  This can be done by repeated feasibility testing of a set of linear inequalities of the form $\mathcal{S} \land \Psi \ge c$, where $c$ is a constant.  In particular, you use binary search to find the largest value of $c$ such that $\mathcal{S} \land \Psi \ge c$ is feasible.

Very roughly speaking, binary search can be expected to succeed within $O(\lg n)$ iterations.  Therefore, testing for feasibility can't be more than $O(\lg n)$ times faster than maximizing an objective function.

Practice

I don't know of any more efficient way to test for feasibility of a set of linear inequalities, than simply to solve a linear program using standard linear solvers.  Basically, you pick any old objective function, and use the linear solver to maximize it subject to the set of linear inequalities.  I don't know of any procedure that is faster in practice than this straightforward approach.