We claim that there exists a messy permutation of $\{1, 2, \dots, n\}$ if and only if $n$ is a power of $2$.

First suppose that there is some messy permutation $(a_1, a_2, \dots, a_n)$ of $\{1, 2, \dots, n\}$. There must be some $j$ such that $a_j \equiv 2a_2 - a_1 \pmod{n}$. If $j \ge 3$, then $n \mid a_j + a_1 - 2a_2$, which contradicts because we have assumed that the permutation is messy. If $j = 2$, then $a_2 \equiv a_1 \pmod{n}$ which is not possible. So $j = 1$ and $2a_2 \equiv 2a_1 \pmod{n}$. Now if $n$ is odd, we get $a_2 \equiv a_1 \pmod{n}$, which is again impossible. Therefore, we get there is no messy permutation for odd values of $n$.

On the other hand, suppose that $(a_1, a_2, \dots, a_n)$ is a messy permutation and $d$ is a divisor of $n$. Set $m = \frac{n}{d}$. We remove the numbers in the permutation which are not divisible by $m$ to get $(a_{i_1}, a_{i_2}, \dots, a_{i_d})$ where $m \mid a_{i_j}$ for each $j$. Now $(\frac{a_{i_1}}{m}, \frac{a_{i_2}}{m}, \dots, \frac{a_{i_d}}{m})$ is a permutation of $\{1, 2, \dots, d\}$ modulo $d$. We claim that this permutation is messy. Assume to the contrary, there are $p < q < r$ among $i_k$'s such that $d \mid \frac{a_p}{m} + \frac{a_r}{m} - 2\frac{a_q}{m}$. This implies $n = dm \mid a_p + a_r - 2a_q$, which is impossible because the first permutation was assumed to be messy.

Therefore, if there is a messy permutation for some integer $n$, $n$ is not divisible by an odd number other than $1$ and so $n$ must be a power of $2$.

Finally, we construct a messy permutation of $\{1, 2, \dots, 2^t\}$ by induction on $t$. Obviously, $\{1, 3, 2, 4\}$ is a messy permutation for $t = 2$. Suppose that $(a_1, a_2, \dots, a_{2^t})$ is a messy permutation for $n = 2^t$. Now consider the sequence
$$(b_1, \dots, b_{2^{t+1}}) = (2a_1 + 1, \dots, 2a_{2^t} + 1, 2a_1, \dots, 2a_{2^t})$$
This sequence is a permutation for $n = 2^{t+1}$. We claim this permutation is messy. If $2^{t+1} \mid b_i + b_k - 2b_j$ for some $i < j < k$, then $k \ge 2^t + 1$ and $i \le 2^t$ because $(a_1, a_2, \dots, a_{2^t})$ was assumed to be messy. Now $b_i + b_k - 2b_j$ is an odd number and so cannot be divisible by $2^{t+1}$. This contradiction shows that $(b_1, \dots, b_{2^{t+1}})$ is a messy permutation and so the proof is complete.