Neppu Kairiku Bushi Road
Sounds a lot like this anime and it is from 2013 but the boy did not die, only the girl did. But that was in the after-credits scene so its possible you did not see it. The robot did stab the girl in the throat and it was considered a myth.
The story takes place in a time when the world is in the pits of despair after being ravaged by a poison called "shinobi" that came to earth via an asteroid. The people run away to the place called "Kairiku," a place that used to be the bottom of the ocean. Here, the people try and protect themselves against the effects of the poison. In such a world, there was a single light of hope. The "Holy Weapon Giga Road" and the legendary warrior "Yagyuu" are needed in order to counter the effects of the poison. Ame, a princess of a fallen nation, stands up in order to save the world.
Ame: The main girl
A former princess/priestess of the country Ise.
Her mother is dead because of a shinobi. She travels with companions and a key to finding a weapon built by men who put an end to the shinobi. She has romantic feelings for Suou. She disappeared in the end.