I use thunderbird at work and I make my extra mailboxes in Thunderbird on my pc. They show up on iphone. I think that's the best way to do it. Make your mailboxes on your pc.
I assume you mean folders and not new mail boxes correct? If so, just create on your normal mail client or if Gmail, etc on their website. Same goes for my Blackberry, I can view folders but they have to be created in Lotus Notes at my office first.
I've been waiting for Google to release a full featured Gmail application so that I can utilize my labels, mailboxes, reply to addresses, signatures, etc