This should do what you want:
global $wpdb;
$wpdb->query("
DELETE FROM $wpdb->usermeta
WHERE meta_id NOT IN (
SELECT MIN(meta_id)
FROM $wpdb->usermeta
GROUP BY user_id, meta_key, meta_value
)"
);
Maybe you should first back up your table, though.