Suppose we have n data observations $\left\{y_i, \underline{x_i}\right\}_{i=1}^n$. We can concatenate the $x_i$ into $X$.
We have $y_i=h^TX + \epsilon_i$.
I understand that, since we have observed it, the matrix $X$ becomes "non-random". $\epsilon_i$ is random noise. However, why do we still say that $y_i$ is random, conditioned on $X$? We have observed $y_i$ as well!
The fact that we have observed $X$ has nothing to do with it being non-random. It seems that it may be not clear for you what is meant in statistics by random variables.
Outcome of a flip of coin may be thought as a random variable. This does not mean that we don't know what was the outcome of the coin toss, but that the outcomes will vary from toss to toss, the behavior of the coin is not deterministic. Even more, in terms of physics, behavior of a coin is deterministic, but nevertheless, there is so many factors that determine each particular toss, that we think of it as of random variable. Other things can be considered as random variables as well, for example human age. There is nothing "random" in human ages, but if you will randomly approach people on the street and ask them for their ages, then there won't be any deterministic pattern in the ages (unless your sample is biased) and so, you could consider age in such experiment as random variable. Moreover, if you adopt broader, Bayesian definition of probability, then the notion of random variables can be extended even to events that are not obviously "random". To make it even more awkward, you can think of deterministic events (e.g. constant) as of random variables by thinking of them in terms of degenerate distribution. As you can see, this has literally nothing to do with the fact that you have observed something or not.
As about regression equation, the formula
$$ y_i = \beta_0 + \beta_1 x_{1i} + \dots + \beta_k x_{ki} + \varepsilon_i $$
may be written in terms of probabilistic model behind it as
$$ \mu_i = \beta_0 + \beta_1 x_{1i} + \dots + \beta_k x_{ki} \\ y_i \sim \mathcal{N}(\mu_i, \sigma^2) $$
so $Y$ is a random variable that follows normal distribution and it's mean is a function of $X$ and $\beta$. Moreover, also $X$ may be considered as random variable and, if using Bayesian approach, also $\beta$'s would be considered as random variables. What we mean by this is that we assume that such variables may take different values and the values have probabilities assigned to them, so we can describe them in terms of their probability distributions. It's about describing data in terms of probabilistic models.
If you were rather interested in what we mean by holding $X$ fixed, you may want to check Linear regression and interpretation of random variables and What is the difference between variable and random variable? threads.
