A robot capable of shifting shape, thus being usable for a wide range of purposes with only software needing to be changed is damn cool. Blocks that crawl over each other are one way of going about this, but require connectors on each block, complicating things.
As the robot can only interact at its surface, a shapeshifting sheet may be a good solution. A triangular mesh of actuators, or perhaps two triangular mesh layers, with actuators between the two layers, for better control and rigidity (think of something like the atomic arrangement of a very thin layer of diamond).
Actuators could be something like air muscles, with the 'nodes' where they join being metal rings. The connections between actuators shouldn't allow slop, but as many of them are needed, they should be cheap, and so cannot be precision made - some kind of rubber or spring-based means of connection seems sensible.
The actuators do not need to have a continuous range of motion, two states should be enough, as the position of the sheet usually only needs to be controlled at selected points (contact points). The further an actuator is from one of those points, the less effect switching it between the short and long states has on the position of that point, thus fine tuning of the position of that point can be done by adjusting the actuators in the surrounding neighbourhood.
Most of the mesh would usually have its actuators in the long position, saving the high density of actuators for areas where more precise manipulation is needed, and the number of contact points is high. Another useful result of this is that if the edges of the sheet have connectors, these can easily be attached while the mesh is expanded by another piece of mesh in the compact form, allowing sheetshifting robots to split and join as well as the crawling block designs.
Programming the thing could be complicated, tho. Perhaps the driver could accept positions where manipulation is to be performed, with estimates of the force the robot needs to be ready to apply, and areas the tobot must keep out of, use these to search for rough sheet configurations fulfilling these constraints, and use parameters of the curvature to control the average numbers of actuators in the long and short states in different parts of the mesh.
In areas where precise manipulation is being performed, once the contact points are in approximately the right place, fine tuning could take place successively further from the contact points. A combination of simulated annealing, and a database of effects of different combinations of actuator states in small clusters may be useful.
Precision would not be great, especially over long distances, but adjustable compliance should be quite possible, and if necessary the thing could be studded with rangefinders pinging each other.