You could use the wp_head hook and inject your <style> tag directly into the <head>. Note: make sure you’re firing the wp_head() function in your template (which you should be doing already).
add_action('wp_head', 'random_background_image_wpse_83275');
function random_background_image_wpse_83275() {
$images = array(
'/path/to/image1.jpg',
'/path/to/image2.jpg',
'/path/to/image3.jpg',
'/path/to/image4.jpg',
);
$image = $images[rand(0, count($images)-1)];
echo '
<style>
html {
background: url("' . $image . '") no-repeat center center fixed;
-webkit-background-size: cover;
-moz-background-size: cover;
-o-background-size: cover;
background-size: cover;
}
</style>';
} // END function random_background_image_wpse_83275
Edit
Another option is to dynamically generate the stylesheet, and randomly choose $image in that file. Then you’d inject your stylesheet <link …> via wp_enqueue_scripts hook (yes, wp_enqueue_scripts), and enqueue with wp_enqueue_style.