How far do I need to move to break Nether Portal link?

The distance that your new portal needs to be away from the old one isn't terribly large, only 128 blocks, but it's measured in terms of the destination world; every block in the Nether is worth eight in the overworld, meaning you'll need to move around 1024 blocks or so away to keep a new portal from joining the one that already exists in the Nether.

I say "around 1024 blocks or so", because the existing portal on the nether side may already be some distance away from the location that would best match up with the existing Overworld portal.

There are, however, a few other options. You could try building a bridge across the lava on the Nether side. Painful and awkward, but once across, you could build a new Nether portal on that end, destroy the Nether-side one that exists (just punching it to turn it off should suffice), and hope that the new Nether-side portal successfully connects to your existing one. Alternatively, you might be able to make a suicide run through the portal, destroy the island so it's no longer a valid spot (and also destroy the portal on that side, too), then once you die and respawn on the Overworld side, a quick trip through should trigger the creation of a whole new Nether-side portal, which might not be in such a poor location.

According to the Minecraft Wiki's entry on Nether Portals:

First, the game converts the entry coordinates into destination coordinates as above: The entry X- and Z-coordinates are floored, then multiplied or divided by 8 (or 3) depending on direction of travel. The Y-coordinate is not changed.
Starting at these destination coordinates, the game looks for the closest active portal. It searches a bounding area of 128 horizontal blocks from the player, and the full map height (128 for the Nether, 256 for the Overworld). This gives a search area of 257 blocks by 257 blocks, at the full height of the dimension being traveled to. An active portal for this purpose is defined as a portal block which does not have another portal block below it, thus only the 2 lowest portal blocks in the obsidian frame are considered. A single portal block spawned in and placed using server commands would be a valid location.
If a candidate portal is found, then the portal will teleport the player to the closest one as determined by the distance in the new coordinate system (including the Y coordinate, which can cause seemingly more distant portals to be selected). Note that this is Euclidian distance, not taxicab distance. Note that a portal above Y=128 in the Overworld will generally not be found unless there are no lower portals nearby. The distance computation between portals in range is a straight-line distance calculation, and the shortest path will be chosen, counting the Y difference.

Distance is calculated in the dimension that you are going to, you you need to multiply by 8. 128*8=1024. Because the portal might have been adjusted, you need to go even further away, say 1100 blocks. This will spawn you somewhere else in the Nether. Another thing to consider is that you could make a minecart system in the Nether, which will take you to the main land in a considerably short amount of time. The same could be done with a bridge for horses and the like.