If I understand the question correctly, the answer is no. 

Let $H$ be a star-shaped graph. (I.e. a vertex $v_0$ and $n$ vertices $v_1,\dots,v_n$, with edge set $(v_0,v_i)$ for $1\leq i\leq n$.) Because $H$ is a tree, every path is unique, so $H$ has the desired property. (For any edge $(v_0,v_i)$, take the path consisting of only that edge.) 

However, it's not possible to add an edge and preserve the property. Any new edge $(v_i,v_j)$ will force a triangle, and the new edge will not have the desired property: any path of length 2 containing it gets from one of its vertices to $v_0$ (or vice versa), but there is a path of length $1$ not containing it that does the same. Similarly, the path $(v_i,v_j)$ of length $1$ can be replaced by the path $(v_i,v_0),(v_0,v_j)$ to avoid this edge.

Furthermore, adding subsequent edges will not solve the problem. Any path of length $2$ containing $(v_i,v_j)$ (wlog, say $(v_i,v_j),(v_j,v_k)$) can be replaced by $(v_i,v_0),(v_0,v_k)$).