How can I run a python script before anything else?
There is a checkbox in the Python controller which seems to be suitable for your needs. It's tooltip says "Mark controller for execution before all non-marked controllers (good for startup scripts)". See screenshot:    



Since you did not mention that you already tried this - you may want to check this option on the controller carrying your scene-defining script.