Detecting Galaxies
Let's look at the example of UDF 423, one of the brightest galaxies in the Hubble Ultra Deep Field. It has an apparent magnitude of around 20, and an estimated distance of 7.7 billion light years (well outside of our supercluster). This gives it an absolute magnitude of somewhere around -21.8, making it only around three times brighter than the Milky Way (at magnitude -20.9). Since it's clearly resolved in the UDF, we can treat that as a good estimate for the level of detail we'd need to achieve in our observations to see the Milky Way directly.
The instrument that Hubble used to capture the UDF is the ACS (Advanced Camera for Surveys), with a resolution of around 0.05 arcseconds. The main instrument on JWST is NIRCAM, with a similar resolution and sensitivity.
The exposure for which the sensitivities are calculated is around 10,000 seconds, and the field of view is 4.4 arcseconds square. This means that a single JWST would take around 3000 years to scan the whole sky at that resolution.
Speeding it Up
Of course, we only need to find a couple galaxies that we recognize. Due to the huge number of them, the probability that we see a familiar one is actually pretty high. Once we are confidant of the location of one or more, we can start concentrating our search on a specific sector of sky, and the speed at which we start locating galaxies will be superexponential.
Recognizing Galaxies
As "BrettFromLA" says, we likely wouldn't recognize galaxies by visual comparison, especially since many would appear in different orientations (one which was once edge-on could now appear face-on). Galaxies would instead be matched by their brightness and spectra. This only gives us a fuzzy match, but
Other Sources
Although pulsars make good candidates for locating ourselves (since they are uniquely identifiable by their period) they are generally too dim to be visible billions of light years away. We can look at quasars, which do not have as clear identifying features, but are significantly brighter.
The Sloan Digital Sky Survey identified most known quasars over around 35% of the sky, and took just ten years to complete. A network of telescopes could cover the whole sky in just a few years. Again, the quasars would be matched by their spectra. After our location is pinned down by the quasar survey, we can use spaceborne telescopes to locate the Milky Way.