Here's another approach:
(*This time we look at the actual value, so we use a function that \
has a special case for "x" and doesn't disturb any other values*)
AnotherReplacer["x", position_] := ColumnBasedFn[Last@position];
AnotherReplacer[value_, _] := value
(*MapIndexed will provide the position info we need.*)
MapIndexed[AnotherReplacer, data, {-1}]
This produces (again)
{{12, 27, 19, 44}, {11, ColumnBasedFn[2], 13, 43}, {ColumnBasedFn[1],
56, 23, 60}, {15, 37, 19, 52}, {10, 31, 21, ColumnBasedFn[4]}, {18,
40, 22, 43}, {15, 50, 28, 56}, {21, ColumnBasedFn[2],
ColumnBasedFn[3], 46}, {20, 39, 25, 51}, {ColumnBasedFn[1], 36, 23,
56}, {ColumnBasedFn[1], 27, 21, 39}, {14, 32, 20, 46}, {22, 40,
ColumnBasedFn[3], 49}, {ColumnBasedFn[1], 31, ColumnBasedFn[3],
44}, {ColumnBasedFn[1], 18, 21, ColumnBasedFn[4]}, {16, 23, 21,
34}, {27, 26, 23, 59}, {17, ColumnBasedFn[2], ColumnBasedFn[3],
35}, {13, 21, 20, 48}, {11, 51, 18, 54}}