WordPress actually uses a Built-in Post Type for Attachments ( called attachment ) so you can use some of the same functions like get_the_title() which is what you’re looking for. Though, I did take some liberties by modifying your code below, using a foreach instead of a for loop:
$gallery = get_post_gallery( 7, false ); // Attempt to get Post Gallery
if( ! empty( $gallery ) ) { // IF Gallery Exists, proceed
$imageIds = explode( ',', $gallery['ids'] ); // Get an array of Gallery IDs
$randIds = array_rand( $imageIds, 20 ); // Randomize array
foreach( $randIds as $imageId ) { // Foreach instead of For, just easier
$image = wp_get_attachment_image_src( $imageId, 'large' );
echo '<li><img src="' . $image[0] . '" title="' . get_the_title( $imageId ) . '" /></li>';
}
}