What approach should I take for this URL structure?

There are several ways to set this up. I´ll explain how I would do it, using as much of WordPress default settings and functionality to keep things simple.

Post Types

I´d start with creating 2 custom post types: trainings and coaching. The name of the post type will be added to the URL, so now your courses are accessible via:

example.com/trainings/postnamename
example.com/coaching/postname

Taxonomies

To group the courses together you can create custom taxonomies.

You didn´t specify how you want to order these posts and if the taxonomies are the same for both courses but let´s say you want to order all trainings courses by level: beginner, intermediate and advanced.

In that case you could create the taxonomy level containing the 3 terms: beginner, intermediate and advanced.

When you register the taxonomy you can specify which post types can use this taxonomy and what the URL should look like.

Use something like this:

 register_taxonomy('levels', array( 'trainings' ), array(
    'hierarchical' => false,
    'labels' => $labels,
    'show_ui' => true,
    'update_count_callback' => '_update_post_term_count',
    'query_var' => true,
    'rewrite' => array( 'slug' => 'trainings/level', 'with_front' => false ),
  ));

to generate URL´s like this:

example.com/trainings/level/beginner      // taxonomy archive of all beginner courses
example.com/trainings/level/intermediate  // taxonomy archive of all intermediate courses
example.com/trainings/level/advanced      // taxonomy archive of all advanced courses

Note that WordPress needs the name of the taxonomy (level) to distinguish a taxonomy from the course post type.

I hope this helps. Also as said before, I´m sure there are more ways to approach this.