The user story format is pretty flexible.

“As a (type of user), I want (some feature), so that (some goal)”

I've seen this format used successfully at my workplace. For example:

"As a System Administrator, I want copies of the product catalog sent daily to our Sales Partners so that these partners always have the most current version of our product catalog"

In this example:

1. A feature is defined. The feature might take the name Partner Extract, for instance. It might be implemented as an ETL job that runs nightly to create data files that are made available to Sales Partners via SFTP.

2. The user story embeds the roles. The two roles identified are System Administrator and Sales Partner.

3. Incorporating non-functional requirements is easy. The above example includes one non-functional requirement: the product catalog updates must be daily. Requirements that address how much, how fast or how often are non-functional requirements. I like to refer to these requirements as "quality attributes". Here is another example of a user story that expresses a quality attribute:

As a Call Center Representative, I want customer search to return the result in 2 seconds or less (on average) so that customers are not left waiting on the phone.

Write user stories for reliability, security, capacity or any other quality that is deemed important.

Feature Dependencies

You have identified some legitimate limitations of user stories. They are unordered and there is no guarantee they will be independent. In fact, the might be interdependent-- a chicken-and-egg problem. I believe that all non-trivial projects require documentation to supplement the user stories. I watched the agile team here at work create activity diagrams (flow charts) of the business process. These diagrams were used to analyze the feature dependencies. Another approach might be to create PERT diagram in a big all-day session with the customer. In the end, some other artifacts will be necessary to support the user stories.

Epic!

A narrative that describes the scope of a project is a good idea. There should be something like a statement-of-work or a project charter. No serious project should be without one. These documents provide a starting place for identifying user stories. These document help answer tough questions like "What should be the priority of this feature?"

Metadata

After 15 years in the business, I have an opinion about meta-data. In general, it should be avoided. A few reasons include: after a month, no one knows if it is accurate; no one knows if it was updated; it is extra work to create it; you can't predict what metadata will be useful. Most meta-data is a distraction. I like to track owner, author, priority, estimate of effort, and date of last modification. Beyond that, I fight hard to keep meta-data out user stories and use cases.

Benefits (so that...)

I have an opinion about this as well. :-) Including the benefits is vital. Often, users will request a feature without having though about its value. No matter how good an agile team is, the project will fail if it implements unimportant stuff at the expense of more critical functionality. Also as a developer, I do a better job coding a feature if I know how it fits into the big picture. Here is a real-life example of a requirement without justification: "The system shall prevent transactions with EIP and a gift card from occurring.". Huh? What is EIP? Why do I care? Why does anyone care? I don't know. Understanding the context would have been helpful before I went to the business analyst for clarification.

Even worse is when no one remembers why the user story was written. Do we still need this one? Has the business process evolved to the point where this user story is invalid? Does anyone know? These conservations waste time. It gets suckier if the the author of the user story has left the company.

Measurement

Here is an example of user story that is not measurable:

As a Call Center Representative, I want the system to be fast so that customers are not left waiting on the phone.

How fast is fast? A millisecond? A tenth of a second? Ten seconds? Nobody knows. Nobody wants to be wrong so no one every even makes a guess.

Compare that user story to this one:

As a Call Center Representative, I want customer search to return the results in 2 seconds or less (for average daytime call volumes) so that customers are not left waiting on the phone.

This user story is testable. Average day time call volume can be determined from log files. Performance testing can be conducted to determine if the requirement has been met. Even better, the users and developers have agreed on the success criteria well in advance of the end of the project. Testable requirements are a beautiful thing.

They are very generic term actually. There is many way to interpret them, varying in the literature and how people see them. Take everything I say with a huge grain of salt.

Usually, an Epic comprise a very global and not very well defined functionality in your software. It is very broad. It will usually be broken down into smaller user story or feature when you try to make sense of it and making them fit in an agile iteration. Example :

Epic

• Allow the customer to manage its own account via the Web

Feature and User Story are more specific functionality, that you can easily test with acceptance tests. It is often recommended that they be granular enough to fit in a single iteration.

Features usually tend to describe what your software do :

Feature

• Editing the customer information via the web portal

User stories tend to express what the user want to do :

User story

As bank clerk,
I want to be able to modify the customer information
so that I can keep it up to date.

I don't think there is really a hierarchy between the two, but you can have one if you want or if it fit how you work. A user story can be a specific justification for a feature, or a specific way to do it. Or it can be the other way around. A feature can be a way to realize a user story. Or they can denote the same thing. You can use both : User stories to define what bring business value and feature to describe constraint of the software.

User story: as a customer, I want to pay with the most popular credits cards
Feature support the GOV-TAX-02 XML API of the government.

There is also the question of scenario, which are usually a way a Feature/User story will be executed. They usually map cleanly to a specific acceptance test. For example

Scenario : Withdrawing money
Given I have 2000$ in my bank account
When I withdraw 100$
Then I receive 100$ in cash
And my balance is 1900$

That is how we define those terms where I work. Those definitions are far from a mathematical definition or a standardized term. Its like the difference between a right wing politician or a left wing politician. It depend where you live. In Canada, what is considered right wing may be considered left-wing in the United State. It's very variable.

Seriously, I wouldn't worry too much about it. The important is that everyone on the team agree on a definition so you can understand each other. Some method like scrum tend to define them more formally, but pick what work for you and leave the rest. After all, isn't agile about Individuals and interactions over processes and tools and Working software over comprehensive documentation?