Just check for the thumbnail, and if it's not set, use the first image from the gallery instead. Something like this:

    $size = 'thumbnail'; // whatever size you want
    if ( has_post_thumbnail() ) {
    	the_post_thumbnail( $size );
    } else {
    	$attachments = get_children( array(
    		'post_parent' => get_the_ID(),
    		'post_status' => 'inherit',
    		'post_type' => 'attachment',
    		'post_mime_type' => 'image',
    		'order' => 'ASC',
    		'orderby' => 'menu_order ID',
    		'numberposts' => 1)
    	);
    	foreach ( $attachments as $thumb_id => $attachment )
    		echo wp_get_attachment_image($thumb_id, $size);
    	}
    }


Basically, if no featured image exists, then has_post_thumbnail() will return false. So you call get_children to get the attached images for this post. Note numberposts = 1, so it only gets the first one. Then you output that image using wp_get_attachment_image.

Note that I used the foreach even though I'm only getting 1 image here. This is because get_children returns an array of posts, regardless of how many posts it's returning. so I'm "looping" through an array of size 1. If there's no images, the array will be empty and so nothing is output.

If you don't like using get_children, then a similar new WP_Query could be constructed to get the first attachment image in a similar manner.