Allow users of my plugin to define their own shortcode rather than use mine?

Save the shortcode name in an option, and use that when you add the shortcode:

add_shortcode( 
    get_option( 'your_plugin_option', 'default_shortcode_name' ), 
    'your_shortcode_callback'
);