To set the environment on the remote side, you will need to do calls on the remote side. Try writing and uploading a wrapper script which does this env setting, e.g.
import subprocess
import sys
args = sys.argv[1:]
env = dict(zip(args[::2], args[1::2]))
subprocess.call(['python', 'script.py'], env=env)
Now you just have to pass this information in your original call, e.g.
subprocess.call('ssh -i <identify file> username@hostname '
'python <script_on_linux_machine> %s %s' % (key, value))
Or some more extensible method of converting a dict to the required format.