Until now (march 2012), using gmail, it is impossible to search for / filter unlabeled e-mail messages. I think I have a workaround for this: select all the email messages and label them with “U”  (as “UNLABELED”) and especially prepare an automatic filter that will automatically applies this label to all further incoming email. Then start selecting the first label (for example “AAA” label) and clear/remove the “U” label from those messages… then continue like that until you reached the “ZZZ” label. This is only for the first time you do the job.
All the “U” messages are “unlabeled”. Of course this is only a workaround, but I’ve never seen this suggestion before. Let me know what you think about it, if it works for you.