A window can only receive key events when it's focused:
KeyPress and KeyRelease events are sent to the window which currently has the keyboard focus.
Widget.focus_set() has proven to fail if you press the key before the window is created. This is a conscious effort to prevent focus stealing. To override this, use Widget.focus_force() (delegates to focus -force).
 
Note that the user needs to press Shift after the Enter or mouse click that they used to start the app -- otherwise, it's considered a part of that input. In Windows, I confirmed with Spy++ that the app's window never receives keyboard events in such a case even though it gets focus. .Net's logic to get key state delegates to GetKeyState that also judges by window messages.
 
Then:
- Use 
<KeyPress-Shift_L> and/or <KeyPress-Shift_R> to detect presses of the Shift keys ("Shift" doesn't work, it can only be a modifier). 
- Set a flag to ignore repeating 
KeyPress events as per GUI Button hold down - tkinter of just unbind the keypress handler. 
A proof-of-concept app:
import Tkinter as tkinter
class HoldKeyDetect(object):
    def __init__(self, widget, keys, handler=None):
        """Detect holding `keys` in `widget`"""
        self.widget = widget
        self.handler = handler        
        self.binds = {}
        for key in keys:
            evid = '<KeyPress-%s>'%key
            self.binds[evid] = widget.bind(evid,self.keypress)
    def __del__(self):
        try: self.unbind()
        except tkinter.TclError: pass   #app has been destroyed
    def unbind(self):
        while True:
            try: evid,fid = self.binds.popitem()
            except KeyError: break
            self.widget.unbind(evid, fid)
    def keypress(self,e):
        try:
            if self.handler:
                self.handler(e)
        finally:
            self.unbind()        
class App(object):
    def __init__(self,root):
        self.root = root
        root.focus_force()
        self.h = HoldKeyDetect(root,("Shift_L","Shift_R"),self.set_mode)
        root.after(1000,   # larger than keypress repeat interval + code overhead
                        self.continue_)
        self.mode = False
    def go(self):
        self.root.mainloop()
    def set_mode(self,_):
        print "Shift mode set"
        self.mode = True
    def continue_(self):
        del self.h
        print "Mode=", self.mode
        self.root.destroy()
if __name__ == '__main__':
    App(tkinter.Tk()).go()