Is it possible to customize the layout of Gallery Shortcode?

You may complete override your gallery shortcode using the filter post_gallery. The return is displayed in your page and no further processing of the shortcode is done.

You may iterarate through the image attached to your post to build your own gallery.

See the implementation of gallery shortcode here: http://core.trac.wordpress.org/browser/trunk/wp-includes/media.php#L758

EDIT:
There are some plugins that modify the default behaviour of the gallery shortcode. Search it from the “Add New Plugin” of the backend. Use the string “gallery shortcodes”.

Note: if you want you can use nextgen-gallery to manage your photos. It has numerous plugin to display with other gallery, like Smooth Gallery, Nivo Slider or jQuery cycle.