Very interesting discussion, and right now i am having trouble with the same issue. My product manager strongly advocates labelling every icon on a mobile device, yet most of the apps we tend to point out as cool and aesthetically pleasing (mind it, very important measure to get the eyeballs in a crowded marketplace where your app may not get a second chance) tend to be cautious with the labels. I am all for reducing the redundancy of visual elements on an app if i use it everyday(Afterall, we dont read the gender label on the restroom icon everytime before we enter one). But the key is how sure are you about that. While labelling every icon might provide the necessary clues upfront for the first time, soon they will become redundant as the users play more attention to the content you are presenting. Added to the fact that most app interactions are typically of very short interval in comparison to desktop, on a much smaller screen area, it is a pain to think of those labels and the visual noise they make.
Having said that, I am thinking of a different approach. I am all for reducing the number of action elements on a mobile screen. How about progressively explaining the icons to the user during his initial activity flow inside the app, across each segments of the app. Eventually, when they do the walk through, they will get familiarised with the app and its different sections. Many apps that rely on gestural controls anyways do such interactions to introduce the actions. Can we think of including a section at the end of those help cards to explain the functions of the few icons (3 max) present on the screen?
Another approach is to make the text labels explicitly and modify the layout without the labels when we detect that the user is visiting the app and its diff. sections a min number of times.
Another approach to reduce the criticality of these label less approach is to make sure all the post/get actions which are critical to be labelled always and limit the label less icons to only navigational elements.
Would love to get your feedback on this!