Actually, this is becoming a thing in Germany. From what I understand, they have had to shut down a number of barn-brothels. No joke. Disgusting, but no joke.
Source: Bestiality brothels are 'spreading through Germany' warns campaigner as abusers turn to sex with animals as 'lifestyle choice' http://tinyurl.com/mgut546
In general, no. The verb needs to be in second position.
It is true, however, that "first position" is not limited to a single word--a longer phrase can take first position. So, in that regards, if "
Der Koch mit seinem
Tier" is taken as a single phrase--if we're distinguishing this cook from the cook who doesn't have his animal with him--then the word order should be correct. (Mind you: a Muttersprachler or someone much more learned than I should confirm this.)
Strictly speaking--regardless of the Nominativ--your sentence is incorrect in that you failed to capitalize the first word of the sentence, der, as well as the other noun, Tier.