python: generate a 'diff' dictionary out of two nested dictionaries
To start I'd change the way that you find vd. Instead of looping through the dictionary and checking the keys are the same, just do a lookup of the key.
This may raise a KeyError, and so you'll want to put a guard in for that.

However the rest of your code needs to change.
First if we have a look at your for i in vi1 loop.
You have the comment Check if lists contains only None, but you're making that list?
Don't do this. Ever.
And so I would move the if and else out of that loop:

for i in vi1:
    if i not in vd1:
        ls_uninst.append(i.split()[0])
    elif i in vd1:
        ls_uninst.append(None)

if all(x is None for x in ls_uninst):
    answer[ki] = {}
    answer[ki]['to_uninstall'] = [None]
else:
    ls_final = [x for x in ls_uninst if x is not None]
    answer[ki] = {}
    answer[ki]['to_uninstall'] = ls_final


From this we can see that the for loop should probably be a comprehension, and I'm saying this now [None] is horrible, so I'm removing that from here.
Which would result in:

ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]


After this, you should be able to see that if not vi1 is true not ls_uninst is true too, and so you can merge these ifs.
Resulting in something like:

for kd1, vd1 in vd.iteritems():
    ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
    answer[ki] = {}
    if ls_uninst:
        answer[ki]['to_uninstall'] = ls_uninst
    else:
        answer[ki]['to_uninstall'] = [None]


The if can then become either a ternary, or you can use or. I think or is quite nice here.
But to be honest, you should just remove this if.

You should now have something that looks like:

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        for ki1, vi1 in vi.iteritems():
            for kd1, vd1 in vd.iteritems():
                ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
                answer[ki] = {}
                answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer


This only uses the last vi1 and vd1 to create this list.
So you should use itervalues instead.
Also I'd use all of the values, not just the last.
This can be done by flattening vi.itervalues,
I'd do this by using itertools.chain.from_iterable, but ultimately it's up to you.
I'd also change vd1 to a set.
And all of this results in:

from itertools import chain
flatten = chain.from_iterable

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        vi1 = flatten(vi.itervalues())
        vd1 = set(flatten(vd.itervalues()))
        ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
        answer[ki] = {}
        answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer