How can I alter the [gallery] markup?

Thanks for your replies, Jan & Rarst. They pointed me in the right direction. Here’s what I ended up with.

This disables shortcodes in the content. Perfect for this site & the function gets attached images & spits them out as a list. (I found the function somewhere & slimmed it down a little)

// Removed shortcodes from the content
add_filter('the_content', 'strip_shortcodes');

// Get attached images & spits out a list of them.
function nerdy_get_images($size="thumbnail", $limit="0", $offset="0") {
    global $post;
    $images = get_children( array('post_parent' => $post->ID, 'post_status' => 'inherit', 'post_type' => 'attachment', 'post_mime_type' => 'image', 'order' => 'ASC', 'orderby' => 'menu_order ID') );
    if ($images) {
        $num_of_images = count($images);
        if ($offset > 0) : $start = $offset--; else : $start = 0; endif;
        if ($limit > 0) : $stop = $limit+$start; else : $stop = $num_of_images; endif;
        $i = 0;
        foreach ($images as $image) {
            if ($start <= $i and $i < $stop) {
            $img_title = $image->post_title;   // title.
            $img_description = $image->post_content; // description.
            $img_caption = $image->post_excerpt; // caption.
            $img_url = wp_get_attachment_url($image->ID); // url of the full size image.
            $preview_array = image_downsize( $image->ID, $size );
            $img_preview = $preview_array[0]; // thumbnail or medium image to use for preview.
            ?>
            <li>
                <a href="https://wordpress.stackexchange.com/questions/2393/<?php echo $img_url; ?>"><img src="<?php echo $img_preview; ?>" alt="<?php echo $img_caption; ?>" title="<?php echo $img_title; ?>"></a>
            </li>
            <?
            }
            $i++;
        }
    }
}

This is the call in single.php

<ul>
    <?php nerdy_get_images('medium','0','0'); ?>
</ul>

This spits out a list exactly how I wanted it.

Once again, thanks guys!