A @Victor Domingos's mentions are really usefull in your case, but your real problem - your own code! First of all - take a look at structure of your application and understand, that it's weak, no offence (you even pass a master to a function to destroy it). So I suggest you to read about classes and inheritance in Python (if you don't already) and then take a look here. 
Next stop - your redirector. You reassign sys.stdout.write, but you never preserve it - so it another weak spot. Ok, let's say that now you preserve it, but if we keeping object oriented approach - I would prefer this option.
Also, is it really necessary to destroy the master? For output you can use a Toplevel widget if you destroing master just to avoid two mainloop's. You can even hide root while Toplevel is active. Marvelous, isn't it?
Finally, to answer your question about solution. There're no straight solution, but only one: read and try. You're already answered why mainloop stops everything, but your question is really broad.
I tried to reproduce your full program (2-window app, 1st-user input, 2nd - console-like and some example printing task with thread) and here's a code:
# imports:
try:
    import tkinter as tk
except ImportError:
    import Tkinter as tk
import sys
import string
import random
import threading
# classes:
class ReStdout:
    # common stdout-redirector
    def __init__(self, target_widget, start_redirection=True):
        self.text_console = target_widget
        if start_redirection:
            self.start_redirection()
    def __del__(self):
        self.stop_redirection()
    def __exit__(self, exc_type, exc_val, exc_tb):
        self.stop_redirection()
    def __enter__(self):
        pass
    def flush(self):
        pass
    def write(self, stdout_line):
        self.text_console.insert('1.0', stdout_line)
    def start_redirection(self):
        sys.stdout = self
    @staticmethod
    def stop_redirection():
        sys.stdout = sys.__stdout__
class App(tk.Tk):
    # common tk app
    def __init__(self):
        tk.Tk.__init__(self)
        self.resizable(width=True, height=False)
        self.minsize(width=250, height=25)
        self.some_entry = tk.Entry(self)
        self.some_entry.insert(0, 'You can pass something to Spawner!')
        self.some_entry.pack(expand=True, fill='x')
        self.start_spawner_button = tk.Button(self, text='Start Spawner', command=self.spawn_spawner)
        self.start_spawner_button.pack(expand=True, fill='x')
    def spawn_spawner(self):
        Spawner(self, self.some_entry.get())
    def close_app(self):
        self.destroy()
class Spawner(tk.Toplevel):
    # common tk app - task spawner
    def __init__(self, master, entry_string):
        tk.Toplevel.__init__(self, master)
        self.resizable(width=False, height=False)
        self.preserved_count = threading.active_count()
        self.master = master
        self.master.withdraw()
        self.spawn_task_button = tk.Button(self, text='Spawn Task', command=spawn_task)
        self.spawn_task_button.pack(expand=True, fill='x')
        self.quit_button = tk.Button(self, text='Quit', command=self.close_app)
        self.quit_button.pack(expand=True, fill='x')
        self.text = tk.Text(self, bg='black', fg='white')
        self.text.pack(expand=True, fill='both')
        self.stdout = ReStdout(self.text)
        self.protocol('WM_DELETE_WINDOW', self.close_app)
        # print what have been passed
        print('Users Input: %s' % entry_string)
        # let's spawn something right now
        # after here just for example
        # try to use it w/o after
        self.after(500, multi_spawn)
    def close_app(self):
        if threading.active_count() == self.preserved_count:
            self.stdout.stop_redirection()
            self.master.deiconify()
            self.destroy()
        else:
            # code to handle threads
            print('\n**** Cant quit right now! ****\n')
# non - class functions:
def multi_spawn(count=1):
    for _ in range(count):
        spawn_task()
def spawn_task():
    task_count = threading.active_count()
    task = threading.Thread(target=lambda: common_task(comment='%d printing task' % task_count,
                                                       iteration_count=random.randint(1, 10)))
    task.start()
def common_task(comment, iteration_count=1):
    # example task wait + print
    task_numb = comment.split(None, 1)[0]
    print('\nTask spawned:\n%s\nIteration count: %d\n' % (comment, iteration_count))
    for _ in range(iteration_count):
        threading.Event().wait(1)
        print('Task: %s \t Iteration: %d \t Generated: %s' % (task_numb, _ + 1, generate_smth()))
    print('\nTask %s completed!' % task_numb)
def generate_smth(size=6, chars=string.ascii_uppercase + string.digits):
    # generate random
    return ''.join(random.choice(chars) for _ in range(size))
# entry-point:
print('Just another example from SO')
app = App()
app.mainloop()
print('Beep')
As you see - I never get stucked (when I don't needed it) in mainloop, because I create threads on events: __init__ of "Spawner" (thanks to inheritance) and a button click event. Of course, it's just one approach from many, but I wish that now your problem is clearer to you.