It seems to be true for $n=3,5,8,9,10$ and then all integers $n$ from $12$ to at least $100$.
EDIT: Yes, this is true.
Let $k^2$ be a square greater than $n$ but less than $2n$. Take $\sigma(j) = k^2 - j$ for $j$ from $k^2 - n$ to $n$. Thus $(\sigma(k^2-n), \ldots, \sigma(n))$ are a permutation of $(k^2-n, \ldots, n)$. This reduces the problem for $n$ to the problem for $k^2 - n - 1$.
Now for all integers $n \ge 27$ there is such a $k$ with $k^2 - n - 1 \ge 12$ (because
$\sqrt{2n} - \sqrt{n+13} \ge 1$), so
once we find such a permutation for all $n$ from $12$ to $26$ we know that there is one for all $n \ge 27$.
Here are suitable permutations for all $n$ up to $26$ for which such permutations exist:
$$ \eqalign{
3 & [3, 2, 1] \cr
5 & [3, 2, 1, 5, 4] \cr
8 & [8, 7, 6, 5, 4, 3, 2, 1] \cr
9 & [8, 2, 6, 5, 4, 3, 9, 1, 7] \cr
10 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6] \cr
12 & [3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4] \cr
13 & [8, 2, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3] \cr
14 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6, 14, 13, 12, 11] \cr
15 & [8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10] \cr
16 & [15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9] \cr
17 & [15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8] \cr
18 & [15, 14, 13, 12, 11, 10, 18, 17, 16, 6, 5, 4, 3, 2, 1, 9, 8, 7] \cr
19 & [3, 2, 1, 5, 4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6] \cr
20 & [15, 14, 13, 12, 20, 19, 2, 1, 7, 6, 5, 4, 3, 11, 10, 9, 8, 18, 17, 16] \cr
21 & [15, 14, 1, 12, 20, 10, 2, 8, 7, 6, 5, 13, 3, 11, 21, 9, 19, 18, 17, 16, 4] \cr
22 & [3, 2, 22, 21, 4, 19, 9, 1, 7, 6, 5, 13, 12, 11, 10, 20, 8, 18, 17, 16, 15, 14] \cr
23 & [15, 23, 22, 21, 20, 19, 18, 1, 16, 6, 14, 13, 12, 11, 10, 9, 8, 7, 17, 5, 4, 3, 2] \cr
24 & [8, 2, 22, 5, 4, 10, 9, 1, 7, 6, 14, 24, 23, 11, 21, 20, 19, 18, 17, 16, 15, 3, 13, 12] \cr
25 & [8, 23, 22, 21, 4, 3, 9, 1, 7, 6, 5, 24, 12, 2, 10, 20, 19, 18, 17, 16, 15, 14, 13, 25, 11] \cr
26 & [15, 14, 22, 21, 20, 19, 18, 17, 16, 26, 25, 24, 23, 2, 1, 9, 8, 7, 6, 5, 4, 3, 13, 12, 11, 10] \cr
}$$
EDIT: For completeness, to show that there are no solutions for $n=2,4,6,7,11$,
in each of those cases we find a set $A$ such that the set $B = \{b: 1 \le b \le n,\ a + b \text{ is a square for some }a \in A\}$ has cardinality less than that of $A$.
$$ \begin{array}{c l l}
n & A & B\cr
2 & \{1\} & \emptyset \cr
4 & \{4\} & \emptyset \cr
6 & \{1,6\} & \{3\} \cr
7 & \{1,6\} & \{3\} \cr
11 & \{4,11\} & \{5\} \cr
\end{array} $$
