HTC Hero, Android 2.1(!)
I have 3 Gmail accounts on my phone — none of them allow me to Synchronize the "All Mail" label. How can I do this?
It appears it's just not possible to sync messages without any label whatsoever, even in Android 4.*
Workaround: Create a filter that applies a label (e.g. ZZ_All) to all emails you receive. Also apply this filter to all pre-existing emails and you have a label you can sync.
Create a new filter f.e. "all" and every mail what goes out or comes in get this lable. Use it for every existing mail and here you go. Change settings on your android device! Dirty variant...