Taxonomy: allow "All values" choice, visible as "All values" in results
Uncheck the Required option from exposed form field settings. Then there will be one more option - Any - will appear in filter dropdown. It will work same as All values. 

You can also change - Any - value in to All Values by using hook_form_alter.

*EDIT :*

So the good structure is : 
- Create a taxonomy vocabulary for the values ;
- Create a level 1 with an "All values" term ; 
- Create a level 2 with all individual values ; 
- Add the taxonomy relationship in the views and load the field taxonomy terms for each result ; 
- Add the taxonomy as an exposed filter with depth ; 
- In the settings of this filter, define a depth of -1, so every individual value chosen will also return the parent value. 
As an example, a chosen region (as a taxonomy term) will return content indexed for "all regions" parent term.