Solution:
Answer: 126

For some choices of the $a_{i, j}$, let $S = \{(i, j) \mid a_{i, j} = 1\}$, and let $S' = S \cup \{(0,0)\}$. Let $C(S')$ denote the convex hull of $S'$. We claim that the problem conditions are satisfied (there exist positive coefficients for the terms so that the polynomial is bounded below) if and only if the vertices of $C(S')$ all have both coordinates even.

For one direction, suppose that $C(S')$ has a vertex $v = (i', j')$ with at least one odd coordinate; WLOG, suppose it is $i'$. Since $v$ is a vertex, it maximizes some objective function $a i + b j$ over $C(S')$ uniquely, and thus also over $S'$. Since $(0,0) \in S'$, we must have $a i' + b j' > 0$. Now consider plugging in $(x, y) = (-t^{a}, t^{b})$ ($t > 0$) into $f$. This gives the value
$$f(-t^{a}, t^{b}) = \sum_{(i, j) \in S} (-1)^{i} c_{i, j} t^{a i + b j}$$
But no matter what positive $c_{i, j}$ we choose, this expression is not bounded below as $t$ grows infinitely large, as there is a $-c_{i', j'} t^{a i' + b j'}$ term, with $a i' + b j' > 0$, and all other terms have smaller powers of $t$. So the polynomial cannot be bounded below.

For the other direction, suppose the vertices of $C(S')$ all have both coordinates even. If all points in $S'$ are vertices of $C(S')$, then the polynomial is a sum of squares, so it is bounded below. Otherwise, we assume that some points in $S'$ are not vertices of $C(S')$. It suffices to consider the case where there is exactly one such point. Call this point $w = (i', j')$. Let $V(S')$ denote the set of the vertices of $C(S')$, and let $n = |V(S')|$. Enumerate the points of $V(S')$ as $v_1, v_2, \ldots, v_n$. Let $i_k, j_k$ denote the $i$ and $j$ coordinates of $v_k$, respectively.

Since $w \in C(S')$, there exist nonnegative constants $\lambda_1, \lambda_2, \ldots, \lambda_n$ such that $\sum_{k=1}^n \lambda_k = 1$ and $\sum_{k=1}^n \lambda_k v_k = w$. (Here, we are treating the ordered pairs as vectors.) Then, by weighted AM-GM, we have
$$\sum_{k=1}^n \lambda_k |x|^{i_k} |y|^{j_k} \geq |x|^{i'} |y|^{j'}$$
Let $c$ be the $\lambda$-value associated with $(0,0)$. Then by picking $c_{i_k, j_k} = \lambda_k$ and $c_{i', j'} = 1$, we find that $p(x, y) \geq -c$ for all $x, y$, as desired.

We now find all possible convex hulls $C(S')$ (with vertices chosen from $(0,0), (0,2), (2,0)$, and $(2,2)$), and for each convex hull, determine how many possible settings of $a_{i, j}$ give that convex hull. There are 8 such possible convex hulls: the point $(0,0)$ only, 3 lines, 3 triangles, and the square. The point has 2 possible choices, each line has 4 possible choices, each triangle has 16 possible choices, and the square has 64 possible choices, giving $2 + 3 \cdot 4 + 3 \cdot 16 + 64 = 126$ total choices.