You can't effectively gain muscle and lose weight at the same time.

This is commonly repeated, but not actually true for people who're just starting out on exercise. It's only when you've already reached a substantial level of fitness that it becomes an either/or proposition.

If you're already heavily overweight though, you're probably better off focusing on losing fat faster rather than worrying about building up muscle at the same time. You may already have a fair amount of muscle under there just from moving around your own body weight.