As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.
$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$
To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.
Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.
Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.
Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since with these fixed values of $y$ the LP will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).