Firstly, if you have a bilaterally symmetric character, you only need 5 facings for 8 way movement as you can mirror left/right and the associated diagonals. If the characters aren't symmetric in this way, then it can lead to funny behavior (imagine a knight whose sword and shield swap hands when he turns from left to right). I can remember this happening in at least one game on the Genesis, though.
There isn't any way to do that without cheating a bit...
1. Render top down. Use sprite rotations to do just that. Pros: simple. Cons: your game will look like Gauntlet and the sprites you see in the action will have no personality whatsoever (BUT you can try the classic techniques of character portraits, or maybe something more advanced like the cartoon panels from the Penny Arcade games).
2. Do a fake 3d game with billboarded sprites. If you play enough of a game with billboarded sprites with multiple facings (say, the enemies from doom), the timing of the face changes of the sprite as your view angle changes allows your brain to infer the true facing of the entity. You could do an "over the shoulder" camera view, and only see the back of your avatar (which might solve other problems, like the number of animation frames you need for it).
The ultimate example of this technique would be Galaxy Force 1/2. It uses layered billboards to achieve depth. I can imagine that this technique could be combined with voxels for some visually interesting results.
3. Draw your sprites such that they can be compressed on one side and stretched on the other without looking bad. This could be used to simulate the character changing aspect relative to you. I've seen this proposed, but I don't think I've ever heard of the technique being used.