How to group posts and get a mixed posts and groups view?

A custom taxonomy makes perfect sense – here’s hoping I haven’t missed something:

$songs = get_posts(
    array(
        'post_type' => 'song',
    )
);

$index = array(); // Build an album_id => songs index
foreach ( $songs as $song ) {
    if ( $albums = get_the_terms( $song->ID, 'album' ) )
        $index[ $albums[0]->term_id ][] = $song;
    else
        $index[ count( $index ) - 1 ][] = $song; // All on it's own. Negative index will not clash with album ID
}

echo '<ul class="songs">';
foreach ( $index as $album_id => $songs ) {
    if ( count( $songs ) > 1 ) // More than one song in this album?
        echo '<li class="album">' . get_term_field( 'name', $album_id, 'album' ) . '<ul>';

    foreach ( $songs as $song )
        echo '<li>' . get_the_title( $song ) . '</li>';

    if ( count( $songs ) > 1 )
        echo '</ul></li>';
}
echo '</ul>';

$index will inherit the order of $songs by however they were queried. When a song belongs to an album, any subsequent songs in that album get added to the stack & will appear in the nested list where the first song is indexed.