Based on @rawr's solution:
set.seed(1)
x <- rnorm(10)
y <- rnorm(10)
z <- letters[1:10]
df<-data.frame(x,y,z)
lab <- df$z
plot(x,y)
p <- par('usr')
l <- legend(p[2], p[4], legend = lab, xpd = NA, bty = 'n')
segments(df$x, df$y, l$text$x, l$text$y, xpd = NA)

But now let's say that each label has more than 1 x,y pair:
set.seed(1)
x <- rnorm(20)
y <- rnorm(20)
z <- letters[10:1]
df<-data.frame(x,y,z)[order]
lab <- levels(df$z)
plot(x,y)
p <- par('usr')
l <- legend(p[2], p[4], legend =lab, xpd = NA, bty = 'n')
lab_df<-data.frame(x=l$text$x, y=l$text$y, z=lab)
do_seg<-function(i){
segments(df[df$z==i,]$x, df[df$z==i,]$y, lab_df[lab_df$z==i,]$x, lab_df[lab_df$z==i,]$y, xpd = NA)
}
lapply(lab,do_seg)
Gives us:
