I'm mildly surprised that nobody (or at least that I've seen) has taken a stickerless, regular Rubik's Cube, get a tray or plate with a very thin layer of paint in it, and then lay one side of the cube down in it. Once one side dries (hanging it up to dry or something), repeat using the rest of the colours. I'd think it would be fairly simple to pull off. If you rough up the sides, the paint should adhere fairly well to the plastic.
Although, I suppose there'd have to be a fair amount of testing to see which paints/etc would work best to avoid flaking or chipping. Or if using a white plastic cube, I imagine there might be a way to dye the plastic on each side.
But in regards to gluing the tiles from the dollar store cubes onto a regular one, I'd probably avoid that. If the dollar store cubes are the ones I'm thinking of, it's a bit smaller than a regular cube, so the tiles would be smaller still since they're not the exact size of the cubie itself on the dollar-store one to begin with. What I'd rather do if I were so inclined to do this, is go to a craft store and get some thin, plastic, coloured sheets. Cutting those into the right size squares and gluing them on would I imagine work a lot better and feel a bit more natural.