When dealing with skewed data and large datasets, requires a combination of techniques.

I name few. The one I am highlighting are extra suggestions on what you did not try yet.:

1. Dynamic partition pruning: Use broadcast join only for non-skewed keys. For skewed keys, partition data to ensure better distribution.
2. Salting with a variation: Using a secondary key in addition to the main_key to generate a more evenly distributed join.
3. Explicit bucketing
4. Filter irrelevant data before joining
5. Broadcast joins for specific conditions

so on and so forth ...