Create new Labels in Gmail App
As of current writing, it seems that it's (still) impossible to create a new label in Android Gmail app. From Google Gmail official support,


  Create a label
  
  
  On a computer, open Gmail. You can't create labels from the Gmail app.
  On the left, click More.
  Click Create new label.
  Name your label.
  Click Create.
  


(Emphasis mine)