How can I make two objects share a vertex, so that when I translate the vertex both objects are deformed? I want to keep two objects, so joining the objects into one is not an option.
Vertices can't be shared unless they are on the same object.
For what you want to do you can use hooks.
On the first object enter Edit Mode (Tab) and select the vertex you want to control. Press the Space Bar, type Hook and select Hook to New Object
That will create an empty in the same place as the vertex. The empty controls that vertex now.
Next step is to make a vertex on the second object control that hook.
Exit Edit mode (Tab) Select the second object and enter edit mode. Press A to deselect everything and select the desired vertex to make it the active vertex.
Exit Edit Mode
Now you need to parent the empty to the active vertex on object two.
To do that select the Empty and while pressing Shift select the 2nd object (Both objects should now be orange), press CtrlP and choose Set Parent to Vertex
Now if you move the vertex on the second object (or the whole object) will make the vertex on the first object move as well.