Linear Model, Distribution of Maximum Likelihood Estimator 
Let $\epsilon_i \sim \text{Exp}(\lambda)$, $\lambda > 0$, and iid for all $i = 1,2, \dots$ Suppose for we have the linear model
  $$ Y_i = \beta X_i + \epsilon_i,$$
  where $X_i > 0$ for all $i = 1, 2, \dots$

I would like to find the distribution of $\hat{\beta} - \beta$ for this model. The cdf and pdf of $Y_i$ is
$$F(y_i) = 1 - e^{\lambda(\beta x_i - y_i)}\mathbb{1}\{y_i \geq \beta x_i\}~~~~~~~\text{and}~~~~~~~f(y_i) = \frac{d}{dy_i}F(y_i) = \lambda e^{\lambda(\beta x_i - y_i)}\mathbb{1}\{y_i \geq \beta x_i\}.$$
Now, the likelihood is
$$L(Y_i; \beta, \lambda) = \prod_{i=1}^n \lambda e^{\lambda(\beta x_i - y_i)}\mathbb{1}\{y_i \geq \beta x_i\}.$$
We want $\beta x_i$ as large as possible without making the indicator 0. Then
$$\beta x_i \leq \min\{y_i\} ~~\Rightarrow~~ \hat{\beta} = \frac{\min\{y_i\}}{x_i}.$$
But I'm not sure how I would go about finding the distribution of
$$ \hat{\beta} - \beta = \frac{\min\{y_i\}}{x_i} - \beta.$$
 A: The problem here is that you have not correctly identified the MLE.  Your likelihood function can be written as:
$$\begin{equation} \begin{aligned}
L_{\mathbf{y},\mathbf{x}}(\beta, \lambda)
&= \prod_{i=1}^n \lambda \exp( - \lambda(y_i - \beta x_i)) \cdot \mathbb{I}(y_i \geqslant \beta x_i) \\[6pt]
&= \prod_{i=1}^n \lambda \exp( - \lambda(y_i - \beta x_i)) \cdot \mathbb{I} \Big( \beta \leqslant \frac{y_i}{x_i} \Big) \\[6pt]
&= \lambda^n \exp \Big( - \lambda \sum_{i=1}^n (y_i - \beta x_i) \Big) \cdot \mathbb{I} \Big( \beta \leqslant \min \Big\{ \frac{y_i}{x_i} \Big\} \Big) \\[6pt]
&= \lambda^n \exp \Big( - \lambda n (\bar{y}_n - \beta \bar{x}_n) \Big) \cdot \mathbb{I} \Big( \beta \leqslant \min \Big\{ \frac{y_i}{x_i} \Big\} \Big). \\[6pt]
\end{aligned} \end{equation}$$
The corresponding log-likelihood function is:
$$\begin{equation} \begin{aligned}
\ell_{\mathbf{y},\mathbf{x}}(\beta, \lambda)
&= \begin{cases}
n \ln (\lambda) - \lambda n (\bar{y}_n - \beta \bar{x}_n) & & \text{for } \beta \leqslant \min \{ y_i/x_i \}, \\[6pt]
-\infty & & \text{for } \beta > \min \{ y_i/x_i \}. \\[6pt]
\end{cases}
\end{aligned} \end{equation}$$
Since this function is monotonically increasing in $\beta$ over the range of the first part, it is maximised at the boundary point $\hat{\beta} = \min \{ y_i/x_i \}$ (which is different to the solution you have given).  Now, to obtain the distribution of this statistic, we can use the fact that:
$$\frac{Y_i}{x_i} - \beta = \frac{\epsilon_i}{x_i} \sim \text{Exp}(\lambda x_i).$$
We therefore have the CDF:
$$\begin{equation} \begin{aligned}
F_{\hat{\beta}-\beta}(t) \equiv
\mathbb{P}(\hat{\beta}-\beta \leqslant t) 
&= \mathbb{P} \Big( \min \Big\{ \frac{Y_i}{x_i} - \beta \Big\} \leqslant t \Big) \\[6pt]
&= 1 - \mathbb{P} \Big( \min \Big\{ \frac{Y_i}{x_i} - \beta \Big\} > t \Big) \\[6pt]
&= 1 - \prod_{i=1}^n \mathbb{P} \Big( \frac{Y_i}{x_i} - \beta > t \Big) \\[6pt]
&= 1 - \prod_{i=1}^n \exp ( - \lambda t x_i ) \\[6pt]
&= 1 - \exp \Big( - t \cdot \lambda n \bar{x}_n \Big). \\[6pt]
\end{aligned} \end{equation}$$
This means that we have the distribution:
$$\hat{\beta}-\beta \sim \text{Exp}( \lambda n \bar{x}_n ).$$
(Note that one consequence of this is that we have the bias $\mathbb{E}(\hat{\beta}-\beta) = 1/\lambda n \bar{x}_n$, so the "bias corrected" version of the estimator is $\hat{\beta}_* = \min \{ y_i/x_i \} + 1/\lambda n \bar{x}_n$.)
