Tibi = "to you." The easiest for now is to remember the construction "Nomen mihi/tibi est."
The longer explanation is that tibi is in the dative case (to/for ...), and "dative + esse (to be)" is a special construction, denoting possession. Literally, the sentence would mean "The name / to you / is / Marcus.", or more fluently "Your name is Marcus.".
If I don't use a sentence with a verb, what would be the most common form? Tibi nomen, or nomen tibi?
"Tibi est" = "you own", so the English translation would be something like "You have a name Marcus".
Souldn't the correct Latin version of "Your name is Marcus" be "Nomen tuum est Marcus"?
Yes, "esse" means to be. But "est" and "deest" with the dative is a commonly used idiom meaning "to have" and "to lack" , respectively. (I just noticed this is already explained in davidvdb's post.)
Nomen tuum est Marcus would be a litteral translation; apparently the Romans did not say like that.
Actually, I'm pretty sure they did. I think the main the point is that the contributors didn't want to introduce possesive pronouns here.
The Romans and later Latin speakers most frequently used the 'dative of possession' construction - 'mihi nomen est', 'tibi nomen est' and not the genitive construction as you are arguing. That is just the idiom in Classical Latin, even if it doesn't translate into modern language well. For example St Pacian in the 4th century CE wrote 'Christianus mihi nomen est' (My name is Christian). The genitive construction, e.g. 'nomen tuum est', is a feature of medieval and later ecclesiastical Latin (although there are probably a few Classical examples knocking around).