I agree that this would be very useful and should be a high priority feature. And... the base framework already supports it! Since Evernote uses HTML as its underlying markup, it already supports heading styles. All they need to do is implement the UI widgets to allow insertion of the <h> tags.
To show that it already supports heading styles, I did this test:
Create an HTML file with heading styles (1, 2, and 3) and regular text (I used Sea Monkey editor)
Open the HTML file with a browser
Copy the content from the browser to a new Evernote note. Note that the Evernote editor renders the heading styles correctly
Optional: Format > Simplify Formatting (makes it easier to view the ENEX data)
Export the note to ENEX
View the ENEX in text editor
Note the <h1> <h2> <h3> styles in the exported note markup
So... how about adding a simple drop down list to create those styles?
The table of contents generator is a great idea as a follow on. As an example, Evernote developers could look at the table-of-contents generator in Sea Monkey's WYSIWYG HTML editor (formerly Mozilla suite, open source). MS Word and Google Docs also have TOC generators.
Incidentally... if you want to have heading styles and table of contents in your notes, the Sea Monkey editor is an option. You just have to copy/paste the note content into Sea Monkey to edit it. Then copy it back. Not elegant.
I attached my HTML test file