You might try a method called "Corner to corner" crochet (C2C).
It seems to be relatively "new" and was something I was really intrigued to find out about. It's often used for making diagonal-style blankets but there are certainly examples of it being used for pixel-style art work.
It has the benefit of being dual-sided and it does allow for semi-regular changing of yarns. Creating your own patterns should be relatively simple with some graph paper and colored pencils/markers. Here's what it looks like:

click image to view project
As you can see, it does a pretty awesome job with pixel-style art and does allow for regular changing of colors. Here's a work-in-progress image for reference:

There's a very in-depth video of how the basic concept of C2C crochet works on The Crochet Crowd. It doesn't explain the more regular color changing process but I think that's something that can be figured out using the instructions for projects like this Christmas tree.
The best part is that the only stitches needed are chains, slip stitches and double crochets, so this should be extremely simple, regardless of skill level.
Also note that, if you're interested in really small scale, you could probably go crazy with this using steel hooks (under 2mm) and cobweb-weight yarn or embroidery floss.