Second version, hopefully correct.
I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.
Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards this, notice that you can reduce to the special case $b=0$: just transform the constraints to
$$
Ax + tb < 0, \\
t < 0
$$
If $Ax < b$ is feasible for some $x$, then $(x, -1)$ is feasible for the problem above. Conversely, if $(x, t)$ is feasible for the problem above, then $\tilde{x} = -x/t$ is feasible for $A\tilde{x} < b$.
This reduction just adds a row and a column to $A$, and a new variable $t$.
Assume then that you are given the problem $Ax < 0$.
Create a data set which has one point labeled red for every row of $A$, and is equal to that row. It also contains the origin $0$, labeled blue. Any hyperplane $H$ separating the red-labeled points from the blue-labeled origin gives a solution to $Ax < 0$: just take the normal of $H$ in the direction of the origin to be $x$.
The final step is to reduce the feasibility problem $Ax \le b$ to the strict feasibility problem $Ax < b$. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let $S$ be an inclusion-maximal set of constraints such that the system $\forall i \in S: (Ax)_i < b_i$ is feasible: we can find $S$ in at most $m$ calls to the oracle (assuming $A$ is $m\times n$). If $S$ contains all constraints, we are done. Otherwise, it is not hard to see that, if $Ax \le b$ is feasible, then for any $i \not \in S$ the constraint $(Ax)_i \le b_i$ must be satisfied with equality for all feasible $x$. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables.
This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal.
