How to let users subscribe and be notified (email) when certain type of content or taxonomy is created?
You could do the subscription by adding the taxonomie term to the user profile. If you don't have to many content types you could add it as a simple select list to the profile. This can be done at admin/config/people/accounts/fields. 

As you sugested you can use Rules to get triggered about creates/updates of content or taxonomy terms. You might have to implement custom rules conditions or actions in PHP in a custom module to get exactly what you need. Check the differen hooks to define your own rules conditions or actions. hook_rules_action_info and hook_rules_condition_info are the most interesting for you.

To lear how to build your own rules code you find many examples in Drupal core and contributed modules.