I've always done this with Javascript:
<?php if(isset($_POST['submit_flag'])){ ?>
<script type='text/javascript'>
window.location='URL';
</script>
<?php } ?>
But now that I think about it, you could easily create another PHP page somewhere in your theme that's not included by the rest of your theme to handle the form data and re-direct back to your form.
I'm also about 98% sure that you can include $wpdb without sending headers by simply requiring "wp-blog-header.php".