Only the first choice is grammatical. This is a complex sentence (I hope). Write a story is a clause which may stand alone. You are then adding a phrase (or clause) to modify "story."
"Beginning with "I hate you." is a perfectly legal participial phrase (I hope).
"Begins with "I hate you." is a perfectly illegal relative clause. (it needs a relative pronoun, like "which.") That is, the clause lacks a subject.