Python 2, 123 122 118 114114 98 Bytes
Man, I wish random
wasn't so expensive (and that we didn't have to filter for spaces). Now we have big savings from being allowed to have cipher characters at the end :) Anyways, here ya go:
from random import*
f=lambda s,n:s and(' '<s[0])*(s[0]+eval(*eval('chr's[0]'+'+chr(randint(32,126))+'*n)[:-1])'*n)+f(s[1:],n)if s[1:]else s