Rhombricks

The rhombic dodecahedron is a polyhedron which has similar symmetry to a cube and can be tiled to fill space like a cube, but is much less boring than a cube. One could conceivably bake rhombic dodecahedral lumps of clay into bricks - even without a mold, it wouldn't be all that hard to cut the clay into shape, given a clay knife or wire that could be guided along a 45-degree angle.

Walls built with rhombic dodecahedra would be a bit lumpy, but sometimes that's desirable (for example, for baffling sound). The walls could merge seamlessly at various nontraditional angles without breaking the tiling. (You could do right angles too, depending on how they're oriented.) You could even continue the tiling into a sloped roof.

There are some other possible space-filling solids, but none that combine regularity and oddness in quite so pleasing a manner.