On concentration of a sum random variable Take a random variable defined as
$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{ij}$ are in $\{-T,\dots,0,\dots,T\}$ with the condition that probability that all $|u_{ij}|<\frac{T}2$ is at most some small $\epsilon\in(0,1)$, $u_{ij}$ are independent of $v_i,v_j$ and $u_{ij}$ might not be independent of $u_{i'j'}$ where either $i\neq i'$ or $j\neq j'$ holds. 
Assume the mean of $r$ is $0$. Variance is at most $n^4b^4T^{2}$.

  
*
  
*What is the probability that $|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T$ holds at any fixed $c\geq2$?
  

We know $P(|r|\leq k\sigma)\geq1-\frac1{k^2}$ and here $k=\frac 1{2n^2}\big(1+\frac1{n^c}\big)<1$ and so useless.


  
*Under what broad conditions on distribution of $r$ can above probability be $>1-\frac1{n^2}$?
  

One possibility is for conditions on random variables that can force cancellations in summation defining $r$ leading to a smaller variance. If $u_{ij}$ are such that $\pm1$ signs occur equally likely with probability $>1-\frac1{n^2}$ then we can expect the variance close to $b^4T^2$ with probability $>1-\frac1{n^2}$ shaving a factor of $n^2$ which leads to desired probability for $|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T$ holds at any fixed $c\geq2$.

If the probability approaches $0$ on some conditions then I am interested in how fast precisely it approaches $0$ on those set conditions. This is implicit in query 1. where I have attempted the asymptotics using Chebyshev.

 A: Under your conditions, $P(|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T)$   will usually go to $0$ as $n\to\infty$. So, the lower bound $1-\frac1{n^2}$ on this probability will be impossible. 
Indeed, for simplicity let $T=1$. Note that $c_b^2:=Var(v_i)=(b^2-1)/12$. Let $u_{ij}:=t_i t_j$, where $t_1,\dots,t_n$ are iid Rademacher random variables (independent of the $v_i$'s), with $P(t_i=\pm1)=1/2$. Let $n\to\infty$. Then 
\begin{equation}
 \frac rn=\Big(\frac1{\sqrt n}\sum_{i=1}^n t_i v_i\Big)^2\to c_b^2 Z^2
\end{equation}
in distribution, 
by the central limit theorem, where $Z\sim N(0,1)$. 
So, for any real $\delta>0$ and all $n>b^2/\delta$,
\begin{equation}
 P(|r|\leq\tfrac12\big(1+\tfrac1{n^c}\big)b^2T)
 \le P(\tfrac{|r|}n\le\tfrac{b^2}n)
 \le P(\tfrac{|r|}n\le\delta)\to P(c_b^2 Z^2\le\delta),
\end{equation}
and the latter probability goes to $0$ 
as $\delta\downarrow0$. 

Addition in response to the OP's clarifications of the question:
For simplicity, let $T=1$. 
Suppose first that the $u_{ij}$'s are nonrandom numbers. 
Then 
\begin{equation}
 Er^2=\sum_{i,j,k,\ell} u_{ij}u_{k,\ell}Ev_iv_jv_kv_\ell=\sum_i u_{ii}^2\mu_4
 +2\sum_{i\ne \ell} u_{ii}(u_{i\ell}+u_{\ell i})\mu_3\mu_1
\end{equation}
\begin{equation}
 +\sum_{i\ne k} [u_{ii}u_{kk}+u_{ik}(u_{ik}+u_{ki})]\mu_2^2
 +\sum_{i\ne k\ne \ell}[2u_{ii}u_{k\ell}+(u_{ik}+u_{ki})(u_{i\ell}+u_{\ell i})]\mu_2\mu_1^2
 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4, 
\end{equation}
where $\mu_p:=Ev_1^p$, $\sum_{i\ne k\ne \ell}$ denotes the sum over all triples $(i,k,\ell)$ of pairwise distinct $i,k,\ell$, and $\sum_{i\ne j\ne k\ne \ell}$ denotes the sum over all quadruples $(i,j,k,\ell)$ of pairwise distinct $i,j,k,\ell$. 
Note also that 
\begin{equation}
 \sum_{i\ne k\ne \ell}u_{ii}u_{k\ell}
 =\sum_{k\ne \ell}u_{k\ell}\sum_i u_{ii}-\sum_{k\ne \ell}u_{kk}(u_{k\ell}+u_{\ell k}).
\end{equation}
Suppose now further that the $u_{ij}$'s are in $[-1,1]\setminus(-1+1/n,1-1/n)$ for all $i,j$ and such that 
\begin{equation}
 \sum_i u_{ii}=0,\quad u_{ij}+u_{ji}=0 \text{ if $j\ne i$, }\tag{*}
\end{equation}
so that
\begin{equation}
 \sum_{i\ne j} u_{ij}=0\quad\text{and hence}\quad \sum_{i,j} u_{ij}=0.
\end{equation}
E.g., if $n=2m$ is even, we can take $u_{ii}=1$ for $i\le m$, $u_{ii}=-1$ for $i>m$, $u_{ij}=1$ if $i<j$, $u_{ij}=-1$ if $i>j$. Let us consider this case in detail. We have 
\begin{equation}
 Er=\sum_{i,j} u_{ij}Ev_iv_j=\sum_i u_{ii}\mu_2+\sum_{i\ne j} u_{ij}\mu_1^2=0+0=0. 
\end{equation} 
So, 
\begin{equation}
 Var(r)=Er^2=n\mu_4+\sum_{i\ne k} u_{ii}u_{kk}\mu_2^2
 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4. 
\end{equation}
Next, 
$\sum_{i\ne k} u_{ii}u_{kk}=\sum_{i,k} u_{ii}u_{kk}-\sum_i u_{ii}^2
=(\sum_i u_{ii})^2-\sum_i u_{ii}^2=0-n=-n$. 
So,
\begin{equation}
 [Var(r)=]Er^2=n(\mu_4-\mu_2^2)
 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4. 
\end{equation}
Repeating this reasoning with $1$ in place of $v_i$, we get 
\begin{equation}
 0=\Big(\sum_{i,j} u_{ij}\Big)^2=n(1^4-(1^2)^2)
 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}1^4, 
\end{equation}
whence
$\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}=0$ and 
\begin{equation}
 Var(r)=Er^2=n(\mu_4-\mu_2^2)=n\,Var(v_1^2)=\tfrac{n}{180} (2 b+1) (8 b+11) \left(b^2-1\right).  
\end{equation}
This is smaller than $n^4b^4T^{2}=n^4b^4$ by a factor of $\asymp n^3$, not just $\asymp n^2$. 
The case of $n$ odd should be very similar. 
Now of course you can take any random $u_{ij}$ (independent of the $v_i$'s) such that $(*)$ holds almost surely or with high enough probability. Is this "packing"/"forcing" condition broad enough? 
