Starfleet Marines do exist. (ST V and VI*) This doesn't ruin Trek as we know it, not by a long shot.
Even James T. Kirk himself once said that Starfleet is a "combined service". I mean, you've got all the different uniform colors, each with its own specialty - command, engineering/security, and science/medical. Marines are just one more branch. What's non-Trek about that?
Starfleet Marines may have a unique rank system and uniform color, but they
are still Starfleet. I don't see anything wrong with that. You've got the Starfleet "navy", which are the starship crews, and Starfleet Marines for ground forces. Simple, logical, effiicient.
* The Starfleet personnel which accompanied Kirk and crew to Nimbus III (in ST V) are Marines. And of course there's COLONEL West in ST VI.