Hi @Anton_Loukine,
Your best option for now would be to create a company record using XML-RPC. The company table is its own entity there so you don’t have to do any hacking in order to add one. See the Company section here for more details.
We are trying hard to keep our new API as RESTful as possible. Part of that includes modeling actionable things in the application (like tagging) as a RESTful resource. The addition of tag_ids on the contact model was a convenience for querying purposes, not for modification. Companies will also be considered a separate resource once they are implemented.