Here's a one line solution.
Put this in your functions.php file:
add_action('template_redirect',
function(){
ob_start();
}
);
ob_start() begins output buffering, so nothing is sent to the browser. That means wp_redirect() works from anywhere, including in a shortcode. When the script terminates, the buffer is automatically flushed and the whole page is sent at that time.
Cheeky ... but it seems to work for me!