Loop through entries with custom ordering, showing one from each category then start loop again
I'd suggest breaking your problem down into code which gathers the IDs of each of the types of entries first, then outputs them....roughly like this (very much untested!! - but should be enough to understand the approach):

{# Arrays to store the IDs of the entries as we find them #}
{% set noDateIDs = [] %}
{% set dateIDs = [] %}

{% for entry in craft.entries.section('heroes').order('date') %}

    {% if entry.date|length %}
        {% set dateIDs = dateIDs|merge([entry.id])} %}
        {# Or of course you could output the data you want here directly but I like to keep my building and output separate for clarity #}
    {% else %}
        {% set noDateIDs = noDateIDs|merge([entry.id])}  %}
    {% endif %}

{% endfor %}

{% set noDateIDsString = noDateIDs|join(', ') %}
{% set dateIDsString = dateIDs|join(', ')  %}

{# Now actually output the dated entries #}
{% for entry in craft.entries.section('heroes').id(noDateIDsString).find() %}

    &lt;article&gt;
        &lt;h3&gt;&lt;a href="{{ entry.url }}"&gt;{{ entry.title }}&lt;/a&gt; - {{ entry.date|date("j") }}{{ entry.date|date("S") }} {{ entry.date|date("F") }} {{ entry.date|date("Y")}} - {% for category in entry.genre %}{{ category.title }}{% endfor %}&lt;/h3&gt;
    &lt;/article&gt;

{% endfor %}

{# Output the undated ones ordered by postDate #}
{% for entry in craft.entries.section('heroes').id(dateIDsString).order('postDate') %}

        &lt;article&gt;
            &lt;h3&gt;&lt;a href="{{ entry.url }}"&gt;{{ entry.title }}&lt;/a&gt;&lt;/h3&gt;
        &lt;/article&gt;

{% endfor %}


This approach is very useful generally in Craft, and is documented really well here in 'Manipulating Craft's ElementCriteriaModel objects with Twig' by Jérôme Coupé of Webstoemp