Get all categories post is not in

Ok. So, the first bit of code is more correct but it has issues nonetheless. Piece by piece…

$categories = get_the_category( $post_id );

$post_id is not set in the code you posted. I assume that value is set earlier in the page somewhere, else that is your first problem.

$nocats = get_terms('category', array('exclude' => $categories) );

The exclude argument will accept an array of term IDs, but that is not what get_the_category() returns. It returns an array of objects. You cannot use that as is. (This, by the way, is the same reason you are having trouble with $excats = implode(',', $categories);. You are trying to convert objects into strings). You need to extract the IDs:

$categories = wp_list_pluck($categories,'term_id');

Then:

$nocats = get_terms('category', array('exclude' => $categories) );

There is one further step: get_terms() by default will only return categories that have posts assigned to them. If you truly want to show all categories you need to add 'hide_empty' => false to your argument list:

$nocats = get_terms(
  'category', 
  array(
    'exclude' => $categories,
    'hide_empty' => false
  ) 
);

Now your code should work:

$categories = get_the_category( $post->ID );
// var_dump($categories);
$categories = wp_list_pluck($categories,'term_id');
// var_dump($categories);
$nocats = get_terms(
  'category', 
  array(
    'exclude' => $categories,
    'hide_empty' => false
  ) 
);
// var_dump($nocats);
foreach ( $nocats as $nocat ) {
  echo $nocat->name;
  echo ","; 
}