From where I'm standing, making all the skills useful in combat would be the neatest solution, IF you could pull it off.
Sabotage could be pretty easy to make combat-ready, since it covers grenades and mines. (... Right?) If you give characters access to more and more powerful grenades throughout the game, and give them all a minimum Sabotage score to use, that would almost make Sabotage a weapon skill in its own right. Weaker, probably, but that would make sense since it's also one of the problem-solving skills.
Medicine covers medikits, which is something but not quite enough to make it balanced. ... Maybe have Medicine give a passive HP Regen bonus while you're fighting? That way anyone with high levels of Medicine would be healing slowly whenever they fought.
That'd leave Charisma and Science, which... are a bit harder, oof. You could maybe use Science as a minimum on some of the more alien weapons in the game? (Not only do you need Heavy Weapons to use that Marada Swiss Army Knife, you also need Science to figure out how the thing works in the first place!
) Couldn't use that too often, since you wouldn't want to overshadow the weapon skills, but it could come into play sometimes. Or maybe you could research and build better weapons with the skill, but that gets away from actual combat a bit. Charisma could maybe give a passive bonus to the whole party, but that could get complicated in a hurry.
Another possibility... I don't know how well this would work, but I'll throw the idea on the table and see what you two think about it. If Charisma and Science are the only two skills in the game that you can't tie to combat in a big way, then you might even that out with colony building. Science logically could deal with a lot of the ways you get energy and resources, and Charisma logically could cover the actual running of the base in some ways. If that part of the game sometimes had problems crop up that needed a Science or Charisma check, and if a character told you at the beginning that would happen, it would go a long way toward making those two valuable even if they weren't really combat skills. You'd have to be careful on how you balanced that, but it'd be a possibility.
I dunno. Game balance isn't something I'm great at, but hopefully that's helpful in some way.