Learn Russian: Девушка необычной красоты приехала из столицы. - A girl of unusual beauty arrived from the capital.

This is the "genitive of qualitative description." Instead of using an adverb and an adjective (like необычно красивая девушка - an unusually beautiful girl), Russian often uses an adjective + noun in the genitive case to describe a defining characteristic. It translates literally as "a girl of unusual beauty."

Why use приехала instead of пришла for "arrived"?

The verb приехать specifically means to arrive by vehicle, which is the logical assumption when traveling from the capital. Прийти (past tense: пришла) would mean she arrived on foot.

Why do we use the preposition из for "from" here, rather than от or с?

The choice of "from" depends on the preposition used for "in" or "to." Because you say "in the capital" using в (в столице), the corresponding reverse preposition is из. If the location took на (like на Кавказ), you would use с (с Кавказа). От is mostly used for moving away from a person or a specific point.

Could we change the word order and say Необычной красоты девушка приехала из столицы?

You could, but it would sound highly poetic, like a line from a fairy tale or classic literature. In standard Russian, a genitive descriptive phrase almost always comes immediately after the noun it modifies.