Попробуйте это:
keys = ['key1', 'key2', 'key3']
words = u'word1 word2 word3'
vals = words.split()
d = dict(zip(keys, vals))
И затем, если вы хотите получить пары ключ / значение в строке, как в вашем примере:
' '.join(sorted(k + ':' + v for k,v in d.items()))