Do I need to add the new domain to my own web hosting first before connecting it here, for email hosting?
Nope, no need for that.
I should add as a second answer:
While not necessary, having a website at the domain can improve your inbox delivery. I have witnessed spam filters at third party services that judge a mail domain for having no website.
And I would like to add that having a newly registered domain can also decrease delivery. I know the service we use at our company takes this into the mix.