Libertarians don't argue against the state protecting citizens from coercion and fraud. They don't argue against the existence of a state; they are minarchists who argue that providing protection against coercion and fraud is the only valid cause for the state to pursue.
Now, if you really mean anarcho-capitalists, who argue against the state entirely, then their answer is that private protection agencies can provide protection better than a state can. The argument is that the state is essentially a monopoly on protection and that, by abolishing it, we create a free market for protection. Free markets are seen, from the classical liberal position, as always being better, both better serving the customers and doing so more efficiently. So the private protection market, being more efficient than the state monopoly, could necessarily prevent anything the state could.
You can read more on the ancap view in Rothbard's Libertarian Manifesto. Note that, when it was written, libertarian was a broader word than it is now. It encompassed any view with classic liberal foundations that opposed the state. The argument Rothbard is making would be considered anarcho-capitalist in modern terminology.
It seems you want a hypothetical view of how this would work. I'm concentrating on how to privatize the market for armed forces of the type that fight overseas wars, though I would question whether such a thing could be maintained in a free market. (I personally don't think it would be profitable -- too few people interested in funding it when the funding comes out of their pocket. But, of course, it is up to the market to decide what is profitable and what is not.) Supposing there would be demand for it, there would be companies that would attempt to fill that demand. They would propose goals to people interested in paying them, and those with popular goals (and a good track record) would be paid. They could then work just like any other military contractor that already exists. This is better in that, there is not a monopoly and that funding is voluntary. If a privately funded military contractor sucks at accomplishing their goal, they loose funding and potentially go out of business. There is a feedback mechanism that directly ties resources allocated to the actor with their performance. This doesn't exist with a minarchist state that publicly (i.e. involuntarily) funds war. Taxes collected aren't directly tied to performance (or tied at all if you take today's situation in the US as empirical evidence), so there is no direct feedback. Caveat: If the state is voluntarily funded and doesn't exclude competition in the protection market, then it is a non-issue.
