Regarding Pach's original question: Bing's house deals with the analogous question of collapsibility. It is an example of a contractible non-collapsible space. For that problem it is known that if you allow both collapses and anti-collapses, every contractable space can be reduced to a point. This follows from "Simple homotopy theory". I dont know if this result of simple homolopy theory extends to animals built from cubes but they might.
The modified higher genus question seems easier since you allow steps that changes the topology of the animal.