Nat, there is no easy way of doing it via PHP, so my suggestion would be to use javascript instead — a script that loops through all galleries and appends the gallery index to rel attribute of each image within that gallery. Something like this should work:

jQuery('.gallery').each( function(g) {
    $('a', this).attr('rel', function(i, val) { return val + '-' + g; });
});

Here is a working example of this idea.