This morning I found the following post on reddit /r/emacs: Evil mode on a vt100 and I recalled having the same issue with terminal Emacs in xterm. By default, xterm emulates VT102, and behaving like VT100, will not send Alt/Meta key to Emacs without this workaround.

In short, the workaround to send M-x in evil-mode even if Alt/Meta doesn't work is to use this combo: \ Esc-x. \ will temporarily suspend evil-mode and Esc-x is the same as M-x. The same will work with C-u M-x: type \ C-u Esc-x.

I wasn't satisfied with this, we are using Emacs, after all ;) How about we can call M-x directly as evil-mode ex command? Sure, run this:

(evil-ex-define-cmd "mx" 'execute-extended-command)

How about C-u M-x (M-x with prefix)? Yup:

(evil-ex-define-cmd "mx-cu"
  '(lambda ()
     ;; must be interactive
     (interactive)
     (execute-extended-command '(4))))

Now, every time I want to get M-x without that suspend-escape-x magic, I just hit :mx. To get C-u M-x, I run :mx-cu.