Simple short range object proximity identification using capacitive sensing
For the reason given in JRE's answer, a straight up capacitance measurement won't work. The chip you linked makes several simultaneous capacitance measurements, so you could have several measurement points on the cube, and a unique pattern of present and absent plates on the other cube to sense.  This isn't going to work well though, for several reasons:


The sensors can only spot the plates when they are up close. How close? Roughly the separation between sensors.
The unique pattern of plates would look wrong to the sensors if the blocks are slightly off centre, or rotated.  You could fix this by giving the pattern of plates translational and rotational symmetry, but then you're going to need a lot of sensors to distinguish a small number of cubes.
The sensors will probably not handle interference well.  What's the capacitance of the floor they are sitting on, for example? It could be hard to predict.


An alternative approach using capacitors would be to have one large plate on each face of each cube. When close together, high frequency signals can be transmitted between plates, but if there is a big gap, or the plates don't face each other, the signal would be attenuated.  Each face of each cube would transmit it's identity as a digital signal encoded on the high frequency carrier.  You'd probably have to alternately 'speak' and 'listen' on each face.