Current status:

Created a new trait

Code:
;------------------------------------------
Trait WallBuilder
    Characters spy

    Level WallBuilder
        Description WallBuilder_desc
        EffectsDescription WallBuilder_effects_desc
        Threshold  1 

;------------------------------------------
Trigger wallbuilder
    WhenToTest CharacterTurnEnd

    Condition AgentType = spy
          and FactionCultureType barbarian
          and SettlementBuildingExists >= stone_wall

    Affects WallBuilder  1  Chance  100
Created a background script:
Code:
script
	
	monitor_event CharacterTurnEnd AgentType = spy
		and Trait WallBuilder >= 1
		and SettlementName Patavium
		console_command create_building Patavium stone_wall_prerequisite
		console_command add_money -3000
		terminate_monitor
	end_monitor
	
	while TrueCondition
	end_while

end_script
Added the building:
Code:
building stone_wall_prerequisite
{
    levels stone_wall_prerequisite
    {
        stone_wall_prerequisite requires factions { barbarian, } and hidden_resource stone_wall_pre
        {
            capability
            {
            }
            construction 0
            cost  3000
            settlement_min town
            upgrades
            {
            }
        }
    }
}
Edited the require clause of the larger walls:
Code:
 requires factions { ct_carthage, eastern, parthia, egyptian, greek, roman, } or building_present_min_level stone_wall_prerequisite stone_wall_prerequisite
This works fine so far, I was able to build stone walls in Patavium after changing descr_strat so that it is a city and spying in Rome ;)
One'd have to do this for every city on the map but that's okay, you can copy&paste and only have to change the settlement name.
The downside of this is that the player may wonder why he just lost 3000 denarii, I'm planning to advance an advice telling him.

I haven't done much more testing yet, I'll post another update this evening.