How to get posts ordered by using their categories?

Before answer I want to say that your code is not really wrong but can be improved:

  1. why run 2 queries when you can run only one?
  2. caller_get_posts is deprecated, use ignore_sticky_posts, instead
  3. get_terms has not title_li nor show_count argument. Moreover $taxonomy is the first argument and do nothing in the $args array (second argument). Seems your arguments are intended wp_list_categories function.
  4. you get the terms from mahlakategooriad taxonomy, but you do no use them in the template. Maybe don’t you post all the code?
  5. You set $wp_query to null before effectively fill it? Why? Moreover you use wp_reset_query that is not needed on custom query. Use wp_reset_postdata, instead.

Let’s anwer.

The workflow I will follow is run one posts loop, put in a helper array the posts using their category slug as key. During the loop I also put in another variable the first sticky post.

When array is filled I start loop through it and output the markup.

// get posts
$args = array(
  'post_type' => 'produktid',
  'posts_per_page' => -1,
  'orderby' => 'date', 
  'order' => 'ASC' ,
  'ignore_sticky_posts' => true
);
$my_query = new WP_Query( $args );

// init helper vars
$first = null;
$sticky = null;
$ordered = array();

// loop
while ( $my_query->have_posts() ) : $my_query->the_post();    
  $terms = get_the_terms( get_the_ID(), 'mahlakategooriad' );
  $term = array_shift($terms); // get first term
  global $post;
  if ( ! isset($ordered[$term->slug]) ) $ordered[$term->slug] = array();
  $ordered[$term->slug][] = $post;
  if ( $my_query->current_post == 0 ) $first = $post;
  if ( is_null($sticky) && is_sticky() ) $sticky = $post;   
endwhile;
wp_reset_postdata();

// get the array of term slugs and order it by name
$terms = array_keys( $ordered );
sort( $terms );

// get the big thumbnail and print it
$featured = $sticky ? : $first;
if ( ! empty($featured) ) {
  global $post;
  setup_postdata($post);
  echo '<div class="main small">';
  echo '<h1><a href="' . get_permalink() . '">' . get_the_title() . '</a></h1>';
  the_content();
  echo '</div>';
  $big_img = get_the_post_thumbnail( $featured->ID, 'tooted-big' );
  if ( ! empty( $big_img ) ) printf('<div class="big-pic">%s</div>', $big_img);
}
wp_reset_postdata();

// the loop
echo '<div class="tooted">';
if ( ! empty($terms) ) { foreach ( $terms as $term ) {
  $ordered_posts = $ordered[$term];
  $term_obj = get_term_by('slug', $term, 'mahlakategooriad');
  printf('<h3>' . __('Products in %s') . '</h3>', $term_obj->name ); 
  global $post;
  foreach ( $ordered_posts as $post) {
     setup_postdata($post);
     $thumb_id = get_post_thumbnail_id( get_the_ID() );
     $plink = get_permalink();
     $title = get_the_title();
     if ($thumb_id) {
       $thumb = wp_get_attachment_image_src( $thumb_id, 'tooted-thumb' ); 
       $big = wp_get_attachment_image_src( $thumb_id, 'tooted-big' ); 
       echo '<div class="toode">';
       printf(
         '<a href="%s" class="toote-thumb" data-link="%s"><img src="%s" alt="%s" /></a>',
         $plink, $big[0], $thumb[0], esc_attr($title)
       );
    }
    printf(
      '<a href="%s" title="%s" class="toote-title">%s</a></div>',
      $plink, esc_attr($title), $title
    );
  }
  echo '<div class="clear"></div>';
} }
wp_reset_postdata();
echo '<div class="clear"></div></div><div class="clear"></div>';