Filter by content type and shared taxonomy terms
To create the view

Create a view with appropriate fields/whatever.
Add the first argument Node: Type.
Add the second argument Taxonomy: Term.
For the second argument select Transform spaces to dashes in URL.

To create the listing page
Option 1
Bite the bullet and create the page in code. You just need to iterate over the content types and terms, creating the links as you go.
Option 2
Create a normal view that lists the taxonomy terms. Use link rewriting in the view to output a link that's contains the term name and content type, and is easily identifiable. Eg. custom_term_list/news/International Politics. Use custom_url_rewrite_outbound() to translate this to /news/international-politics. Gotta be careful not to slow the site down here.
Option 3
Use a terms as nodes paradigm. (I think this would work.) Create a content type for which each node will refer to a term. This can be done with taxonomy_node, nat (Node Auto Term), or even content_taxonomy (and maybe others for all I know). Add a computed_field that calculates the name of the term with spaces turned to dashes (or whatever). Then it would be easy to make the listing. If you want the node term to be created automatically when a term's created, then you'll need to use one of the first two modules mentioned.
Those are the only approaches I can think of to create listing pages. I think I'd just go for the first one.