Where the word "with" comes from is unclear to me, it doesn't sound like it's related to either 'med/mit/mee' or 'avec', not even to 'cum'.
Quote from OED:
OE. wið = OFris. with, OS. wið, ON. við (Sw. vid, Da. ved): app. a shortening (peculiar to the Anglo-Frisian and Scandinavian areas) of the Com. Teut. *wider- (see s.v. wither a. and adv. and wither-1), perh. taking place orig. in compounds (cf. with- and the parallelism of OE. wiþcéosan and wiþercéosan to reject, wiþstandan and wiþerstandan to withstand, etc.).
Maybe someone understands that . . .
To translate from "linguist" to "English", in case someone is interested:
"ð" is the voiced form of "th" (so it's to "th" what "d" is to "t" or what "z" is to "s"). "þ" is the letter originally used for what became "th".
*wider- means that the form is reconstructed/guessed from later forms, that is - we don't know the original form, but that's our best approximation. Hence the asterisk. The form is parallel to the modern word "wither".
Originally, the word was possibly part of compounds, which is to say something made up of two combined words, but working as a single word (similar to "bathhouse" or "boytoy"). This can be compared to "with-" and the feature of Old English where various word structures using the same beginning were possible (by analogy or parallel to each other). The relevant examples from Old English are words like "wiþcéosan" (pronounced roughly "with-KE-osan") and "wiþercéosan" ("wither-KE-osan") meaning "reject", as well as "with-stand-an" and "wither-stand-an" meaning "withstand". Basically, it illustrates the use of the parallel "with/wither" as a beginning of multiple words.
As an additional comment, Old English had verbs that were conjugated (they had changing forms, mostly endings, depending on the role in the sentence), "-an" was the default, basic form that was replaced based on the rules of grammar. Modern English mostly dropped verb forms, unlike other Germanic languages.
DISCLAIMER: it's been almost a decade since I last used any of my linguistic knowledge for any reason and my knowledge is spotty, I might be getting some things horribly, terribly wrong.