The answer is yes, such a graph does exist, and I'll sketch how to construct such a graph. The ideas for the construction come from the paper:
Bowler, N., Erde, J., Heinig, P., Lehner, F. and Pitz, M., 2016. A counterexample to the reconstruction conjecture for locally finite trees. arXiv preprint arXiv:1606.02926.
Let's suppose we have already built a locally finite connected graph $H_i$, and we have a list of the non-edges (where we've left countably many gaps for later steps) such that for the first $i$ non-edges $e_1,e_2, \ldots e_i$ there is an isomorphism from $H_i \cup e_j$ to $H_i$ for $j \leq i$.
Let us further suppose that there is an infinite set of leaves in $H_i$, coloured red and blue, such that each of the isomorphisms send red leaves to red leaves and blue leaves to blue leaves. The idea will be that, if we extend $H_i$ to a graph $H' \supset H_i$ by only gluing bits on at coloured leaves, and gluing the same bit at each red leaf, and the same bit at each blue leaf, then these isomorphisms will extend to ones from $H' \cup e_j$ to $H'$.
Take the next edge in the ordering $e_{i+1}$ (which we may assume is not adjacent to any red or blue leaf). We will build a locally finite connected graph $H_{i+1} \supset H_i$ such that
- For each $j \leq i+1$ there is an isomorphism from $H_{i+1} \cup e_j$ to $H_{i+1}$, and for $j \leq i$ this extends the isomorphism from $H_i \cup e_j$ to $H_i$.
- There is an infinite set of leaves in $H_{i+1}$, coloured green and yellow, such that all the above isomorphisms preserve the colours of the leaves.
To do so, let us write $\overline{H_i}$ for $H_i \cup e_{i+1}$. We build a graph as follows, we take a copy of $H_i$ and a copy of $\overline{H_i}$ and we join them from a red leaf in $H_i$ to a blue leaf in $\overline{H_i}$, adding a green and yellow leaf in the middle.
We want to extend this to a graph in such a way that, 'behind' every leaf coloured red in the picture, the same graph appears, and similarly for blue leaves. We can achieve this by recursively sticking a copy of the part of the figure behind the red leaf (so, the path in the middle and $\overline{H_i}$) onto every red leaf in the picture and a copy of the part behind the blue leaf (the path in the middle and $H_i$) onto every blue leaf, where in each copy we keep the colour of the leaves (so that later in the recursion we glue further copies onto those leaves)
After a countable number of steps we obtain a graph $H_{i+1} \supset H_i$. By construction we have glued the same graph behind each red leaf of $H_i$ and similarly behind each blue leaf of $H_i$, and so the isomorphisms from $H_i \cup e_j$ to $H_i$ will extend to isomorphisms from $H_{i+1}$ to $H_{i+1} \cup e_j$. Furthermore, these will preserve the colour of the yellow and green leaves.
However there is also an isomorphism from $H_{i+1} \cup e_{i+1}$ to $H_{i+1}$. Indeed, in the figure if we map $H_i \cup e_{i+1}$ to $\overline{H_i}$ (via the 'identity'), this will preserve the colour of the leaves, and the graph $H_{i+1}$ has the property that the same graph appears `behind' each red leaf, and similarly for the blue leaves, and so this map extends to an isomorphism of $H_{i+1}$. Again, it's easy to see that this isomorphism preserves the colour of yellow and green leaves.
Since at each stage our graphs are locally finite, there are only countably many non-edges, and so we can add the new non-edges to our list, still leaving countably many gaps, in such a way that the next non-edge we want to deal with isn't adjacent to any yellow or green leaf. Then we repeat the process with the next edge $e_{i+2}$ in the list, with the red and blue edges now yellow and green.
In this way we build a sequence of graphs $H_0 \subset H_1 \subset H_2 \ldots$, and if we take the direct limit of this sequence then we claim the resulting graph $H$ will have the desired property.
Indeed, any non-edge $e$ in $H$ was a non-edge in some $H_i$, and so was on our list of non-edges at stage $i$, and so in a later stage, say $H_k$ we ensured that $H_k \cup e$ was isomorphic to $H_k$. However, by our construction there is a `compatible' sequence of isomorphisms from $H_j \cup e$ and $H_j$ for each $j \geq k$ (in that, they restrict down to each other), and so the direct limit of these maps is an isomorphism from $H \cup e$ to $H$.
