Instead of echoing out these images, just store them as strings inside an array and choose one of the array items at random.
<?php $headerimage_options = get_option('headerimage_options' );
$images = array();
$images[] = '<img title="'.get_bloginfo('name').'" src="'.esc_url( $headerimage_options['image'] ).'"/>';
$images[] = '<img title="'.get_bloginfo('name').'" src="'.esc_url( $headerimage_options['image2'] ).'"/>';
$images[] = '<img title="'.get_bloginfo('name').'" src="'.esc_url( $headerimage_options['image3'] ).'"/>';
$v = array_rand($images);
echo $images[$v];