This recurrence brings to mind the wave equation. Denote by $L$ the lattice $\newcommand{\bZ}{\mathbb{Z}}$ $L=\bZ^2$ and $t:L\to\bZ$ the "time" function
$$ t(x,y)=x+y,\;\; (x,y)\in L. $$
The "initial hypersurface" $S_0$ is defined by the equation $T=0$. A point $p=(x,y)\in L$, $t(p)>0$, is uniquely determined by its time $t(p)=x+y$ and its position $u(p)=x-y$. $\newcommand{\bC}{\mathbb{C}}$
Consider a function $a:L\to\bC$ satisfying your recurrence relation. Its value at the point $(x,y)$ with time $t=(x_0,y_0)$ is only affected by its values in the region $|x-x_0|\leq t$ on initial hypersurface $S_0$.
For any $R>0$ define
$$S_0(R,t)= \lbrace (x,y)\in L;\;\;x+y=t,\;\;|x|\leq R\rbrace, $$
and
$$ m(R, t) :=\max_{(x,y)\in S(R, t)}|a(x,y)|. $$
Your recurrence implies
$$ |a(x,y|\leq \frac{1}{2}\bigl(\; |a(x-1,y)|+|a(x,y)|\;\bigr),\;\;\forall (x,y)\in R. $$
This implies immediately that
$$ m(R,t) \leq m(R+1, t-1). $$
In particular, for $t>0$ we have
$$ m(R,t)\leq m(R+t,0). $$
This controls the size of the "future" values of $a$, i.e., the values of $a$ in the region $t\geq 0$. If we assume that
$$ m(R,0)\leq Ma^R, $$
for some $c\geq 1$, $M>0$ then we deduce that
$$ M(R,t)\leq M a^{R+t},\;\;\forall t\geq 0. $$
In particular, if $a$ is bounded along $S_0$, it will stay bounded in the future. The past values seem a bit more difficult to control. I have to think more about this.
I thought more about this and I reached a conclusion: the past cannot be determined from the initial conditions at $t=0$.
Suppose that we have a function $a: \bZ\to \bC$ satisfying your recurrence conditions and such that, at $t=0$ is zero. What could be the values on the time slice $t=-1$?. Denote by $A$ the restriction of $a$ to the slice $t=-1$. We set $\newcommand{\ii}{\boldsymbol{i}}$
$$ A_n = a(n,-n-1),\;\;n\in\bZ. $$
Set $c:=e^{\ii\theta}$. The recurrence relation implies
$$A_n +c^n A_{n-1}= 0,\forall n\in\bZ $$
so that
$$ A_n = A_0 (-c)^{\ell(n)},\;\;\ell(0)=0,\;\;\ell(n+1)-\ell(n)=n,\;\;\forall n\in\bZ $$
This shows that we can generate solutions of your recurrence that are far from temperate for $t<0$. Here is how you do it.
Fix a function $f_0 :\bZ\to\bC$. This is the initial condition
$$ a(x,-x)=f_0(x),\;\;\forall x\in \bZ. $$
Define $g_{-1}:\bZ\to \bC$ by requiring
$$ g_{-1}(0)=0,\;\;g_{-1}(x)+cg_{-1}(x-1) = 2f_0(x),\;\;\forall x\in \bZ. $$
Pick a constant $M_1>0$ and then set
$$ f_{-1}(x) = M_1 (-c)^{\ell(x)} +g_{-1}(x),\;\;\forall x\in \bZ. $$
Observe that $f_{-1}(0)= M_1+1$ and
$$ f_{-1}(x)+c^xf_{-1}(x-1)=2f_0(x). $$
Proceed inductively. Suppose we have produced functions $f_{-1},\dotsc, f_{-k}:\bZ\to \bC$,
$$ f_{-j}(0)= M_j+1,\;\;j=1,\dotsc, k. $$
We determine $g_{-k-1}:\bZ\to \bC$ by requiring that
$$ g_{-k-1}(0)=0,\;\; g_{-k-1}(x)+c^xg_{-k-1}(x-1)= 2f_{-k}(x),\;\;\forall x\in \bZ. $$
Pick a positive constant $M_{k+1}$ and then set
$$ f_{-k-1}(x) := M_{k+1}(-c)^{\ell(x)}+ g_{-k-1}(x),\;\;\forall x\in\bZ. $$
For $k>0$ we define inductively $f_k:\bZ\to \bC$
$$ f_k(x)=\frac{1}{2}\bigl(\; f_{k-1}(x)+c^xf_{k-1}(x-1)\;\bigr). $$
Finally define $ a:\bZ^2\to\bC $ by setting
$$ a(x,y)= f_{x+y}(x),\;\;\forall (x,y)\in\bZ^2. $$
The function $a$ satisfies the recurrence relation and
$$ a(0, -k) = M_k+1,\;\;\forall k\in \bZ_{>0}. $$
By choosing the sequence $M_k$ suitably, e.g. $M_k = k^{k!}$, your guaranteed a non-temperate behavior for $a$.
Remark 1. Suppose we are given a function $f_0:S_0\to\bC$, a sequence of points $p_n=(x_n,y_n)$, $n>0$, so that $t(p_n)=x_n+y_n)=-n$ and a sequence of complex numbers $C_n$, $n>0$. Then there exists a unique solution $a$ of the recurrence equation satisfying the "initial conditions"
$$ a(p_n)= C_n,\;\;\forall n>0, $$
$$ a(x,y)= f_0(x,y),\;\;\forall (x,y)=S_0. $$
Remark 2. To obtain estimates for the growth of this solutions in the past one needs to understand the growth of the solution of the following initial value problem. Given $f:\bZ\to \bC$ let $u:\bZ\to\bC$ be the solution of the initial value problem
$$ u(x)+c^xu(x-1) = 2f(x),\;\; x\in \bZ, $$
$$u(0) =0. $$
Note that
$$ u(1)= 2f(1),\;\; u(2)= -c^2 u(1) + 2f(2)=-2c^{\ell(2)} f(1)+2f(2), $$
$$ u(3)= -c^3u(2)+2f(3)= 2f(3) -2c^3f(2) +2c^{\ell(3)} f(1) $$
$$ = 2(-c)^{\ell(3)}\bigl(\; (-c)^{-\ell(3)} f(3)+(-c)^{-\ell(2)}f(2)+(-c)^{-\ell(1)} f(1)\;\bigr). \tag{1} $$
The pattern is now clear and one can see that
$$ u(n)\leq 2\bigl( |f(1)|+ \cdots +2|f(n)|\;\bigr). $$
This is an optimal bound which is achieved. Suppose for example that
$$ f(n)= (-c)^{-\ell(n)} r_n,\;\; r_n>0 $$
Then
$$u(n)= 2(-c)^n (r_1+\cdots + r_n), \;\; n>0. $$
The solution with the temperate initial condition
$$ a(n,-n)= (-c)^{\ell(n)} ,\;\;n\in\bZ, $$
$$ a(0,-n)=0,\;\; n>0, $$
is non-temperate because $|a(1,1-t)|=2^t$, $\forall t\geq 0$.
In general is satisfies an estimate of of the type
$$ a(n,n-t)\sim 2^t \frac{n^t}{t!},\;\; t>0,\;\; n>n(t). $$
Remark 3. If the "initial" condition for $a$ is the $\delta$ function concentrated at the orgin, then $a$ has exponential growth in the past.
More precisely, if $a$ satisfies the recurrence and the initial conditions
$$a(x,-x)=0,\;\;\forall x\in\bZ\setminus 0,\;\;a(0,0)=1, $$
$$ a(0,-t)=0,\;\;\forall t<0, $$
then $$|a(1,1-t)|=2^t. $$