Is there a 1/poly(n) or 1/polylogn upper-bound for this tail bound? Is there a good tail bound for $\operatorname{P}\!\Bigg[\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n a_{i,j})^2}{n^2} -1\bigg\vert > \epsilon\Bigg]\,,$ where all $a_{i,j}$'s are iid, with $\operatorname{E}[a_{i,j}] = 0\,, \operatorname{E}[a_{i,j}^2] = 1\,, \operatorname{E}[|a_{i,j}|^3] = \rho\,.$ 
The tail bound can be without any relation to $\epsilon$ but needs to converge to 0 as $n\to\infty\,.$
 A: Let $A:=\Bigg\{\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n a_{ij})^2}{n^2} -1\bigg\vert > \epsilon\Bigg\}\,$ denote the event in question. We will show that 
$\operatorname{P}(A)\le C_{\epsilon}/n$ 
for a suitable constant $C_{\epsilon}$.
If $a_{ij}$ had a finite fourth moment, the argument would be easy. Given only a third moment, we resort to truncation. Observe that 
$\operatorname{P}(|a_{ij}|>n) \le E(|a_{ij}|^3)/n^3=\rho/n^3$,
so   $X_{ij}:=a_{ij}1_{\{|a_{ij}| \le n\}}$ satisfy
$\operatorname{P}(\exists i,j \le n \,  : \, X_{ij} \ne a_{ij})   \le \rho/n$. Therefore 
$A_1:=\Bigg\{\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n X_{ij})^2}{n^2} -1\bigg\vert > \epsilon\Bigg\}\,$ satisfies  
$\operatorname{P}(A) \le \operatorname{P}(A_1)+ \rho/n$. 
Next, we estimate the moments  $\mu_k:=E(X_{ij}^k)$. 
First, $\mu_1=E(X_{ij})=-E(a_{ij}1_{\{|a_{ij}|> n\}})$, so that
$|\mu_1| \le E(|a_{ij}|^3/n^2)=\rho/n^2$.
Second, $\mu_2 \le 1$ and
  $1-\mu_2 = E(a_{ij}^2 1_{\{|a_{ij}|> n\}}) \le E(|a_{ij}|^3/n)=\rho/n$. 
Third, $|\mu_3| \le \rho$ and fourth, $\mu_4 \le n E(|X_{ij}|^3)\le n\rho$.
Thus for each $j$, the column sum $S_j=\sum_i X_{ij}$ satisfies
$E(n-S_j^2) = n(1-\mu_2)-n(n-1)\mu_1^2$ so $|E(n-S_j^2)| \le \rho$ (assuming   $n>\rho$.) 
Moreover,
$\operatorname{Var}(n-S_j^2) \le E(S_j^4)\le n\mu_4 +4n^2 |\mu_3 \mu_1|+3n^2{\mu_2}^2+ 6n^3 \mu_2 {\mu_1}^2 + n^4\mu_1^4 \le 5\rho n^2$, 
provided that $n>\rho$. Here the constant 5 is not optimal, and we used $\rho \ge 1$ to simplify.
Therefore $S=\sum_j (n-S_j^2)$ satisfies (assuming $n>\rho$):
$E(S^2)= \operatorname{Var}(S)+ (E[S])^2 \le 5\rho n^3 +n^2\rho^2\le 6\rho n^3$.
Finally, for  $\epsilon>0$ and  $n >\rho$, we have 
$\operatorname{P}(A_1)=\operatorname{P}(|S|>n^2 \epsilon) \le 
E(S^2)/(n^4\epsilon^2) \le 6\rho/(n\epsilon^2)$,
whence $\operatorname{P}(A)  \le 6\rho/(n\epsilon^2) +\rho/n$.
