Your code doesn't make sense to me. Not only are you redefining values in Data mid-process, as you note, your are also extracting elements down to the third level (Data[[i]][[j + 1 ;; j + 500, 2 ]]) yet you say this is a "two dimensional array."
I shall assume that you want to average all elements in an m by n window, either with or without overlap. Using this data as an example:
a = CharacterRange["a", "x"]"p"] ~Partition~ 6;4;
a // MatrixForm
$\left( \begin{array}{cccc} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{array} \right)$
If you want to take the mean of the following $2 \times 3$ groups:
Partition[a, {2, 3}, 1] // MatrixForm
$\left( \begin{array}{cc} \left( \begin{array}{ccc} a & b & c \\ e & f & g \end{array} \right) & \left( \begin{array}{ccc} b & c & d \\ f & g & h \end{array} \right) \\ \left( \begin{array}{ccc} e & f & g \\ i & j & k \end{array} \right) & \left( \begin{array}{ccc} f & g & h \\ j & k & l \end{array} \right) \\ \left( \begin{array}{ccc} i & j & k \\ m & n & o \end{array} \right) & \left( \begin{array}{ccc} j & k & l \\ n & o & p \end{array} \right) \end{array} \right)$
You could use:
Needs["Developer`"]
PartitionMap[Mean @ Flatten @ # &, a, {2, 3}, 1]
$\left( \begin{array}{cc} \frac{1}{6} (a+b+c+e+f+g) & \frac{1}{6} (b+c+d+f+g+h) \\ \frac{1}{6} (e+f+g+i+j+k) & \frac{1}{6} (f+g+h+j+k+l) \\ \frac{1}{6} (i+j+k+m+n+o) & \frac{1}{6} (j+k+l+n+o+p) \end{array} \right)$
Partition and PartitionMap have the advantage of being flexible and easy to observe, but they are also inefficient for this. (PartitionMap is more memory efficient than Partition, but both end up adding and dividing the same elements many times.)
You can more efficiently perform this particular operation (offsets of one) using MovingAverage once in each direction:
Fold[MovingAverage[#\[Transpose], #2] &, a, {3, 2}] // Factor // MatrixForm
$\left( \begin{array}{cc} \frac{1}{6} (a+b+c+e+f+g) & \frac{1}{6} (b+c+d+f+g+h) \\ \frac{1}{6} (e+f+g+i+j+k) & \frac{1}{6} (f+g+h+j+k+l) \\ \frac{1}{6} (i+j+k+m+n+o) & \frac{1}{6} (j+k+l+n+o+p) \end{array} \right)$
Still more efficient is ListCorrelate, though it is perhaps bit less intuitive:
ListCorrelate[ConstantArray[1/6, {2, 3}], a] // Factor // MatrixForm
$\left( \begin{array}{cc} \frac{1}{6} (a+b+c+e+f+g) & \frac{1}{6} (b+c+d+f+g+h) \\ \frac{1}{6} (e+f+g+i+j+k) & \frac{1}{6} (f+g+h+j+k+l) \\ \frac{1}{6} (i+j+k+m+n+o) & \frac{1}{6} (j+k+l+n+o+p) \end{array} \right)$
For different offsets PartitionMap is the simplest method I know of:
PartitionMap[Mean@Flatten@# &, a, {2, 2}] // MatrixForm
$\left( \begin{array}{cc} \frac{1}{4} (a+b+e+f) & \frac{1}{4} (c+d+g+h) \\ \frac{1}{4} (i+j+m+n) & \frac{1}{4} (k+l+o+p) \end{array} \right)$
PartitionMap[Mean@Flatten@# &, a, {2, 3}, {2, 1}] // MatrixForm
$\left( \begin{array}{cc} \frac{1}{6} (a+b+c+e+f+g) & \frac{1}{6} (b+c+d+f+g+h) \\ \frac{1}{6} (i+j+k+m+n+o) & \frac{1}{6} (j+k+l+n+o+p) \end{array} \right)$
PartitionMap[Mean@Flatten@# &, a, {3, 2}, {1, 2}, {-1, 1}, {}] // MatrixForm
$\left( \begin{array}{ccc} a & \frac{b+c}{2} & d \\ \frac{a+e}{2} & \frac{1}{4} (b+c+f+g) & \frac{d+h}{2} \\ \frac{1}{3} (a+e+i) & \frac{1}{6} (b+c+f+g+j+k) & \frac{1}{3} (d+h+l) \\ \frac{1}{3} (e+i+m) & \frac{1}{6} (f+g+j+k+n+o) & \frac{1}{3} (h+l+p) \\ \frac{i+m}{2} & \frac{1}{4} (j+k+n+o) & \frac{l+p}{2} \\ m & \frac{n+o}{2} & p \end{array} \right)$