It sounds to me like it should be possible to use a 4x4 grid but add a single bit to express whether the letter is shifted up or down by 1px. Then your characters are 4x4 but occupying a 5x4 space.