A key-value datastructure with fast (on average) member move and nearest neighbors search?
An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.