In my opinion for beginners it's no problem to gain muscle and at the same time lose body fat.
It really doesn't matter that much whether you eat low carb or low fat, it's the total amount of calories. Don't get things too complicated. Eat lots of fresh fruits and veggies and add protein sources to that. Try to stay low on fats, they usually are sufficient in your protein sources anyway. Eat often, but small portions. Drink water between the meals. If you gain weight easily, watch carb-loaders like pasta and bread.
For the workout, try to split your cardio from your weight training. Do the basic exercises often but not to muscle failure, try to come close to it but not reach it. Thus, you can train more often in order to burn more fat and will still grow due to the weight training.
Keep it simple
If you have questions left, ask