Paint and paintbrush would be an obvious way to colorize certain blocks in-world rather than via a crafting recipe/machine process. At a minimum, this would be the existing colored blocks (glass, terracotta, wool, concrete) and this process would simply be a much more convenient method to recolorize (since applying paint wouldn't necessarily make sense). If the spirit of the idea was to be more like the OpenBlocks mod's implementation of this, then you could colorize blocks that normally aren't dyeable...like, for example, cobblestone. You would have to mix up the paint (which OpenBlocks stores in a paint can that you can place down and interact with), and you can set the paintbrush to that specific color.
Canvas is another block from the OpenBlocks mod, it's really nothing more than a block that you can color and apply stencils to (so that the paint you apply fills in only the stencil shape). Think of this entire process being like a "draw your own glazed terracotta pattern", as the stencil shape selection is simplistic but can be multiply layered to produce more complex shapes.
I suppose Canvas could also be something that's used in a new functional block called the Easel. It would basically be a an in-world way to create banners, and perhaps this could be expanded to allow for the creation of banner-design-like paintings (versus images selected at random) to hang on a wall.
In all cases, though, this is probably done via the use of tile entities. A small amount of tile entities probably wouldn't hurt anything, being that they're not doing much in the game. A middle-sized vanilla village where every building has been wallpapered with a custom design? That might do something noticeable to your lag situation.