This step-by-step solution works (and it is not so complicated that it seems to be...):
First, convert yor raster into polygons by
ArcToolbox -> Conversion Tools -> From Raster -> Raster To Polygon.
Once new polygons created, identify their coordinates of centroids by Add Geometry Attributes - it creates new culomns in your polygon attribute table with X,Y coordinates of centroid of each polygon.
ArcToolbox -> Data Management Tools -> Features -> Add Geometry Attributed

Now you have X,Y coordinated of every centroid in attribute table of your polygon. You have to save this attribute table as separate file:
Open attribute table, select all rows and export table (to .txt if you want):
Now you have to import this attribute .txt table to directly use XY coordinates to produce a XY points:

From these points, export data as .shp:

and run the Point Distance Tool to measure distances for paires of points (distance 1->9 = distance 9->1)
ArcToolbox -> Analysis Tools -> Proximity -> Point Distance
It produces your distance table. You can verify your results by Measure Tool
