Following up on Martin Büttner's comment this is perhaps best handled using Ordering. We can apply it to subarrays produced by Partition, though we will need to Flatten or Join them. I shall further use PartitionMap to improve memory performance.
A starting array:
SeedRandom[0] a = RandomInteger[9, {4, 6}]; a // MatrixForm $\left( \begin{array}{cccccc} 7 & 0 & 8 & 2 & 1 & 5 \\ 8 & 0 & 6 & 7 & 2 & 1 \\ 0 & 6 & 1 & 2 & 8 & 6 \\ 5 & 5 & 8 & 4 & 5 & 9 \\ \end{array} \right)$
The process:
<< Developer` PartitionMap[Ordering[Flatten@#, 1][[1]] &, a, {3, 3}, 1, 2, 99] $\left( \begin{array}{cccccc} 6 & 5 & 4 & 6 & 5 & 4 \\ 3 & 2 & 1 & 3 & 2 & 1 \\ 3 & 2 & 1 & 4 & 3 & 2 \\ 2 & 1 & 2 & 1 & 1 & 4 \\ \end{array} \right)$
The numbers correspond to placement within:
Partition[Range@9, 3] $\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{array} \right)$
Notes:
- The padding element,
99in the example above, must never be the minimum. - In cases with multiple minimum values the position of the first is used.
If it is vital that the central position always have priority over the neighbors with regard to the minimum value we can simply reorder the elements before Ordering is applied. This changes the meaning of the numbers in the result but since that is arbitrary already it should not matter.
PartitionMap[ Ordering[Flatten[#] ~RotateLeft~ 4, 1][[1]] &, a, {3, 3}, 1, 2, 99 ] $\left( \begin{array}{cccccc} 2 & 1 & 3 & 2 & 1 & 4 \\ 2 & 1 & 6 & 3 & 2 & 1 \\ 1 & 7 & 6 & 9 & 8 & 7 \\ 7 & 6 & 7 & 6 & 6 & 9 \\ \end{array} \right)$
The numbering now corresponds to:
$\left( \begin{array}{ccc} 6 & 7 & 8 \\ 9 & 1 & 2 \\ 3 & 4 & 5 \\ \end{array} \right)$