The debate as to whether it is possible to lose fat at the same time as gaining muscle is a common one. From a scientific point of view it is, in fact, not possible to be in an anabolic state while you are in energy deficit. It is also imperative to be in energy deficit in order to lose body fat. So, from this point of view it is impossible to actually gain muscle, whilst losing fat.
Bodybuilders who are dieting strictly, say for a show, will not be able to gain any muscle while losing their fat to achieve the cut look. The trick is to maintain their muscle, which if training and nutrition are optimal is easily possible, and you need lose no muscle even in the strictest stages of dieting.
However, most of us don't need to diet so strictly. Many of us may want to lose a reasonable amount of fat, but there is no need to lose it so quickly that muscle growth isn't possible. All bodybuilders and athletes who strive for optimum nutrition should be eating a varied choice of food everyday. Such bodybuilders/athletes who are aiming to lose fat, in doing this will have their calorie intake varying from one day to the next; sometimes they will be in energy deficit, where fat loss will occur and sometimes in energy surplus (where they will gain muscle). Furthermore, this will happen during the course of one day; at times they will be in deficit, at times in surplus.
Of course, on this type of regimen, neither muscle gains nor fat loss will be as high as if you were in energy surplus or energy deficit respectively, so the individual need to decide what it their priority. However, as most of you are striving to continually gain muscle, even if you want to shed some fat, this is the best way of achieving your goals.
As to how you would achieve this metabolic state sounds complex, but, in fact, it's far from complex. All you need to do is 'clean up' your diet, reduce portions of the carbohydrate fraction of your meals (but not eliminate them), keep protein high, eat small regular meals and include (more) cardiovascular exercise. From this you must monitor your progress, possibly on the scales and my bodyfat assessment, but more importantly in the mirror and with the critical eyes of your honest friends. If progress on either parameter is not as you would like, you will need to adjust accordingly.
For a sample meal plan of such a regimen see my article on MuscleTalk, not that this is merely an example and will need to be amended to suit you: See the MuscleTalk Losing Fat article.