Suppose my company operates an online game that has the following features:
(1) players find partners to form teams, and the whole game is based on team vs team matches
(2) match result depends on more skill than luck
(3) free to play
(4) players can use real money to purchase virtual items, but those items won't directly influence the chance of winning

My company wants to run an knockout tournament that operates like this:
(1) partcipated teams compete with each other, and the winner proceeds to next match
(2) the final winner is awarded a prize (physical item or cash)
(3) free to join

Now I am concerned about the legal aspects of running such a tournament.

If I ran the tournament in my own country (only local players allowed to join) I would seek advice from local relevant departments about whether it is against gambling laws, whether I need to get license, etc. AFAIK, it depends on factors like free to join, skill / luck ratio, item instead of cash reward, etc.

I would be interested to know about such regulations in your country.

Also, how about run the tournament internationally?

First, you DO need to worry about your own country.

The fact that the winner is given a real-world reward means you need to get a lawyer involved. It may seem like a minor infraction, but running an unregulated gambling system can land you in jail in many countries.

Lawyer, lawyer, lawyer.

Just to reinforce the above, you really need to speak to a lawyer for this one.

It's quite likely that you will need some form of licence or permit and may have comply with gaming regulations, but to get proper and accurate advice you need to speak to a lawyer who knows your local laws regulations.

most of the features you describe are quite similar to online-poker systems and know that to get one of these running quite a few legal hurdles need to be jumped over. So apart from consulting a lawyer you might want to do some online-research about the legal background of online-poker (or any other card game for money). The wikipedia-article on online poker has a part about the legality, which might be a nice starting point.

Also be aware that waiting for new game to become legal or at least regulated by law, can seriously stall your project.