Let's see if I can explain this as thoroughly as possible.
は is the topic particle. It marks one of the following things:
It really doesn't mark much else.
に is a lot of things, but most of them are irrelevant to this question. The important uses are these:
The ren'youkei ('infinitive', which is a terrible term) of the Old and Middle Japanese copula なり
Locative (in Middle and Modern Japanese, only a static locative - it's where something is located, not where something is happening)
-て is a verbal continuative affix that attaches to the ren'youkei. Before Modern Japanese, it had a sense of sequentiality (e.g. 'this and then that'); but these days X-て Y just means 'X and Y' regardless of whether the actions are sequential or simultaneous.
にて, then, is the Middle Japanese dynamic locative. It marks where things are happening (in contrast to where they're located, which is just に). This distinction between static and dynamic locatives is new as of Middle Japanese, and I don't know if anyone can definitively say why this distinction was created. (I personally suspect that it was an attempt to copy Korean's =e/=seo distinction, but that's original research.) I don't know if anyone knows why they picked this particular construction, either, though it is a valid way to say 'exists in a place and then (something else)'. にて has since turned into で through phonetic reduction.
What's にて doing in the copula, then? Japanese (and probably Japonic as a whole) has had a copula of the form locative+あり (modern ある) for as long as we can tell. The original form was なり (from に+あり), though at some point around the end of the 1500s Japanese switched from using に to using にて (>で) as the copula's locative particle. I don't think anyone knows why, sometimes these things just happen. である of course still exists in Modern Japanese, though it's also been phonetically reduced - to だ in the northwest and to じゃ elsewhere, and subsequently from じゃ to や in Kansai and a few other places.
The negative is で(は)ない because the negative of ある is ない. Why is there a topic particle in there? My guess is this: because almost always, when you say 'X is not Y', you're implying that X is something other than Y. It's then the contrastive use of the topic particle - X is not Y (but it is something else). You can get the contrastive use without the negative also, as ではある, though it's much less common. Over time, ではない has become a set phrase - it's not so much that there's something semantically wrong with でない, it's just that ではない is so much more common that it's replaced でない in the few uses where でない might have been preferred, allowing the negative form to be ではない and only ではない.
You can actually hear でない in certain cases, though. Relative clauses in formal speech are one case - since you're not supposed to have topics inside subclauses, you lose the は. (In informal speech, the set phrase effect comes into play again, and the restriction on topics is ignored since no one's thinking of は here as a topic marker at all anymore - it's just part of the phrase.) You can also hear it as an alternative phonetic reduction to じゃない - some areas in the northwest use でない as their everyday negative form of だ.
So in short: it's で instead of に because diachronic change sometimes does things like that, and it's ではない instead of でない because ではない has turned into a set phrase.