When I learned about D3.js this was exactly what I wanted to use it for. Unfortunately, I've mostly avoided web development, so my javascript isn't good enough to quickly code anything up. You're right, though, this could be a good excuse to learn it.
Graph layout algorithms have come to mind for a topic on my blog from time to time. It's a woefully underdeveloped field, and it could be good blog fodder...
My favorite casual text editor is this one [1]. So likewise I imagine a graph editing program that's very simple and one could use it anywhere. Say you click and that creates a new node and a text area pops up for you to type things in. Then you can create a new node, drag to form an edge, etc. The only thing is that I imagine I'd hate working around the force-guided graph layout algorithms the entire time, cause stuff would keep bouncing around. I'd want to be able to drag and drop nodes to move them away momentarily, zoom in and out and pan to focus my attention on some small part of the graph, and then toggle the layout algorithm to snap things back into place.
Everything would be stored locally in the DOM (or, say, in the url), so you could bookmark and share easily, and import/export to JSON or edge-list representations. And... yeah that's about it. I can't imagine wanting colors or styling, but if the design is simple enough you could have plugins for that (and plugins for layout algorithms, etc). I also can't imagine how one would do text navigation on nodes of large degree... Even if you did come up with a system, it would necessarily depend on the graphical layout decisions (which change dynamically) and that would require you to tie the graph data structure to its geometric interpretation, which smells like spaghetti design to me.
It's something to think about. If your ideas are along similar lines, I'd be happy to team up and start a github repo. I just can't commit to working on it all that often.
[1]: data:text/html, <textarea style="font-size: 1.5em; width: 100%; height: 100%; border: none; outline: none; font-family:monospace" autofocus /> (copy and paste this as a url)
EDIT: I suppose if you really wanted a keyboard-based system you could have a text representation of the graph (as a vertex list + edge list) and have the graph update in real time. When you make changes in one side the changes automatically update in the other side. Then you could use keyboard or mouse however you see fit.
(by the way, I love your blog)