Как добавить ключ со значением во вложение к словарю?
1.Users - строка с json`ом, не словарь.
2.Методы работы как с json`ом, так и со словарями - основы и описаны в документации и куче учебного материала.
import json

users = """

{
    "users" : {
        "23423424" : {
            "nums" : [14, 3425, 33, 2],
            "first_name" : "Alex"
        },

        "234442" : {
            "nums" : [33, 1, 99, 42],
            "first_name" : "Gosha"
        }
    }
}

"""

my_dict = {
    "777" : {
        "nums" : [2131, 666, 91, 2],
        "first_name" : "Max"
        }
}

dict_users = json.loads(users) # получаешь словарь из строки джейсона

dict_users["users"].update(my_dict)

print(dict_users) #{'users': {'23423424': {'nums': [14, 3425, 33, 2], 'first_name': 'Alex'}, '234442': {'nums': [33, 1, 99, 42], 'first_name': 'Gosha'}, '777': {'nums': [2131, 666, 91, 2], 'first_name': 'Max'}}}