In a commercial context, yFiles for HTML should be pretty much exactly what you are looking for:
It's a client side Javascript library that uses HTML5 browser technologies like SVG,CSS3 and Canvas, as well as modern Ecmascript features for displaying and editing graph-like structures. It does not depend on any active server components.
It comes with built-in editing capabilities that can be customized to a very high-degree. E.g. if you aren't happy with the default gestures for creating, connecting, or moving elements, if you need a different gesture for zooming or panning the viewport, all of this can be customized. Also it comes with specific support for touch devices and touch gestures.
You can attach any number and kind of data to the elements and optionally display that data in the visualization. The visualization of the diagram elements (nodes, edges, labels, ports, but also the graphical adorners like resize handles, marquee rectangles, etc.) can be fully customized. Adding new elements is easy because at its core, plain SVG is used, so you can leverage existing graphics and third party designer tools to create interactive CSS styled and animated SVG items.
Regarding the storage: Of course the model can be modified and accessed via a Javascript API and at its core the model is Javascript objects. But there are convenience classes and samples on how to populate the graph from XML, JSON data, or angular-observed collections.
Regarding automatic layout capabilities: At the time of writing to my best knowledge the automatic layout algorithms of the library are by far the most elaborate and complete implementations available as native Javascript implementations. This live online demo shows some of the algorithms and some of the configuration options in action. The algorithms support advanced concepts like port-constraints, edge grouping, hierarchical node grouping, integrated labeling, positioning constraints, and many more. The developer's guide gives and introduction to the various available layout algorithms and concepts.
There are demos available that show how to customize the drag and drop gesture and integrate the widget with other Javascript UI frameworks. The library does not come with a toolbar implementation or implementations of other widgets. Instead you can and should consider using a widget toolkit like Dojo, ExtJS, jquery-UI, etc. in order to add widgets like toolbars, context menus, property panels, etc.
In a non-commercial context, finding a library that will do all of this for you, is a lot more difficult. D3 is strong in displaying data quickly and easily, but does not offer out-of-the box strong interaction or layout capabilities. The JsPlumb Toolkit provides nice editing capabilities, but also does not offer layout capabilities. Acceptable layout capabilities are offered by the open-source GraphViz engine. Although it's a C library, there are ways to port that library to make it run as a black-box in Javascript using Javascript source code cross-compilation. This will give you a command-line like interface inside the browser for the algorithms, which is not very convenient, but depending on your requirements may be enough.
Disclaimer: I work for the company that creates the yFiles library, however on SE I do not represent my employer. My posts, thoughts, and comments are my own.