How can I clean out that All Mail folder without removing the items in labels to get space in storage?
In order to remove all email that does not have a label assigned to it, search for any message that does not have a user assigned label. Select all messages that match this search, delete.
If you have email that are also in the inbox that you do not want removed then negate those.
Other options may include the following
has:nouserlabels -in:sent -in:chat -in:draft -in:inbox