The problem you have having is what you actually are doing is to get all the taxonomies that match on every node on your site. A quick hack would be to create a node (doesn't need to actually be published) that contains all of the taxonomy terms, then you could limit the nodes to only that node and you would get a list of all taxonomy terms you want.
Else I would go for one of the options that Henrik Opel suggested, personally I would just make a little custom module for this, and make the queries myself.
Views is a very powerful module, but in some cases, it's actually a lot easier and faster to just do the queries yourself. Especially when the display is not so complicated. You could even use the templates that views has to render your data, if you don't want/need to create your own.