Plugin will sort users by usermeta

If you want best practices of the options you listed use the user meta table.

Adding a column to the users table would be the worst thing you could do – messing with table structure of default WP tables is a no-no.

The other two options would fall somewhere in between – with adding your own table being least preferred.

But why don’t you use the WP_User_Query class?

 $user_by_kin = new WP_User_Query( 
    array( 
        'meta_key' => 'kin_id', 
        'meta_value' => $kin_id, 
        'meta_compare' => '=' 
    ) 
);