'With' or 'By'
'By other means' makes for more colloquial English, whatever the German original. Part of the art of translation is to avoid literalness in the interests of conveying in one language ideas and arguments expressed in another. We say 'By what means will you achieve this?', 'I will have to pursue my objective by other means'. Such sentences are entirely typical when we talk about 'means' in a means/ ends context, and to use 'with' in place of 'by' would jar. Logically, the English 'by' and the German mit have no difference of meaning in the present context.
What is Clausewitz's point?
Clausewitz's dictum is imprecise, hence your questions about it. One might readily argue that war is not a continuation of politics by different means but the discontinuation of politics (in the sense of diplomacy and negotiation) in favour of violence. Neither 'war' nor 'politics' has sharp boundaries of sense or meaning.
One might even reverse the dictum and say that politics is a continuation of war by other means, as when state actors, with no diminution of hostility, shift from violence to diplomacy to achieve their ends. But that's a parenthesis.
When Clausewitz holds that war is a mere continuation of politics by other means, I suggest that the 'mere' is meant to slough off any moral associations. Clausewitz is not concerned with notions such as that of a just war or jihad. He regards war, any war, from a purely instrumental viewpoint.
War, politics and subservience
You ask whether 'for Clausewitz, war is always and necessarily subservient to politics, or merely that politics is not subservient to war?'
'War' is a political term in the sense that war, as opposed to mere fighting, takes place between political units - poleis in Ancient Greece, 'states' or 'nations' in the modern world. You and I cannot go to war ! To probe deeper:
War
War is organized violence
by voluntary, conscripted, or mercenary armed forces; planned by
the leaders of a nation or a group; involves the use of weapons;
aimed at an enemy; and may be offensive or defensive. In the
narrow sense, war is waged by the armed forces of one nation
against the armed forces of another nation. In the wide sense, war
may also be waged by clandestine resistance fighters, guerillas, partisans, terrorists, crime syndicates, warlords and their followers; it may
be civil, religious, ethnic, or tribal; it may take the form of terrorism,
genocide, and massacres; it may be waged by armed forces against a
group of fellow citizens or against some transnational group; the
enemy aimed at may or may not be armed or organized and may or
may not include civilians; and the violence involves killing, disabling,
and generally subduing the enemy. (John Kekes, 'War', Philosophy, Vol. 85, No. 332 (April 2010), pp. 201-218: 201.)
The wide sense seems the most relevant. From Clausewitz's dictum it is tenuous (at best) to conclude that politics is subservient to war. War is an instrument of politics. Indeed, the mere instrumentality of war and its reduction to a means - a vehicle - by which politics can be continued ('by other means') strongly suggest the subservience of war to politics, not the other way round.
As for the other possibility of interpretation, 'war is always and necessarily subservient to politics', it's important to note that Clausewitz does not commit himself to universal ('always') or modal ('necessarily') claims. He would have no need to, even if he did. His central idea - or at any rate the idea central to the dictum - is that a state, nation or ruler pursuing certain goals that conflict with or otherwise bear upon the affairs of another state, nation or ruler should, or at least does, regard war as a part of the toolkit. Politics in the sense of diplomacy, negotiation or bargaining is one tool; war is another. Efficient instrumentality is what matters; we use whichever tool, politics or war, is calculated to achieve our ends.
Interplay
I'd just add that a warlike state, nation or ruler is likely to have a style of politics that fits its belligerency; and that political ideas influence the ways in which war is conducted.
