The minimization with respect to $\alpha$ is easy: Given $\beta$, we can form $\delta_i:=y_i-\beta x_i$; then the optimal value of $\alpha$ is halfway between the maximal and minimal values of $\delta_i$, and the corresponding value of $P$ is half the distance between the two. Let $i_>$ be an index (depending on $\beta$) for which the maximal value of $\delta_i$ is attained, and let $i_<$ be an index for which the minimal value of $\delta_i$ is attained; then
$$
\begin{eqnarray}
\min_\alpha P(\alpha,\beta)&=&\frac{1}{2}(\delta_{i_>}-\delta_{i_<})\\
&=&\frac{1}{2}((y_{i_>}-\beta x_{i_>})-(y_{i_<}-\beta x_{i_<}))\\
&=&\frac{1}{2}((y_{i_>}-y_{i_<})-\beta(x_{i_>}-x_{i_<}))\;.
\end{eqnarray}
$$
Now assume that for a given $\beta$ there is only one index each for which the maximal and minimal values of $\delta_i$ are attained. Then in some sufficiently small neighbourhood of that value of $\beta$ these indices will not change as we vary $\beta$. That means we can decrease $\min_\alpha P(\alpha,\beta)$ by changing $\beta$ in the direction of the sign of $x_{i_>}-x_{i_<}$. Thus, such a value of $\beta$ cannot be the optimal one; that is, the optimal $\beta$ is one for which either the minimal or the maximal value of $\delta_i$ is attained for two different indices. In other words, the optimal $\beta$ is such that some line in the convex hull of the points $(x_i,y_i)$ has slope $\beta$.
Now as we increase $\beta$, $i_<$ increases from $1$ to $n$ and $i_>$ decreases from $n$ to $1$; the value of $\min_\alpha P(\alpha,\beta)$ decreases as these indices move towards each other and then increases again after they've passed each other. The optimal $\beta$ is one where one index for which $\delta_i$ is minimal lies between two indices for which $\delta_i$ is maximal, or vice versa. If the points are in general position, there will be a unique value of $\beta$ with this property.
[Edit:] I just noticed that in the last paragraph I assumed that the points are ordered with increasing $x_i$, but you hadn't assumed that. If they aren't ordered, replace "$i_\lt$ increases" by "$x_\lt$ increases" and "$i_\gt$ decreases" by "$x_\gt$ decreases".