Is there a way to randomize and connect a background and header image?

Here’s some sample code you can use for the header or background. This uses the genesis header hook which you can change to a theme specific hook or WordPress hook.

add_action('genesis_header', 'conditional_header_image');

function conditional_header_image() {

if ( is_tag('your-tag')) {

echo '<div class="home-header"><img src="http://example.com/path/to/image.png" alt="home header image" /></div>';

elseif(is_page() )

echo '<div class="page-header"><img src="http://example.com/path/to/image.png" alt="page header image" /></div>';

    }
}

Untested.

I would look at the code in the Twenty Eleven theme to see how they use random headers and add conditionals to that.