How to store Python Add-In menu customization/configuration in *.esriaddin file?

An .esriaddin file is just a ZIP-compressed archive containing the files that make up your add-in. You can open it with something like 7-Zip to prove this to yourself. The Essential Python Add-in concepts article hints at this.

The layout of your-addin, including definitions of toolbars, menus and buttons, is all stored within the config.xml, whose syntax is not particularly well documented anywhere (though you might check the .NET or, particularly, the Java add-in docs which for some reason have a better-documented dissection of the file).

However, you are not really expected to have to mess with the config.xml and are encouraged to instead use the Python Add-in Wizard to build out your add-in's structure. Presumably you are already using this.

As far as adding a menu to a toolbar, and a button to a menu, it's just a matter of right-clicking the appropriate entries in the wizard and selecting the desired items:

The layout of a Python Addin can be changed by editing/updating the config.xml file.

Also trying to get my head and hands around the various ways ArcGIS can use Python via scripts (.py), ArcToolbox toolboxes (.tbx), Python toolboxes (.pyt), including Python Addins (.py and .xml).

Using the Python Addin Assistant (PAA) will generate a config.xml file that you can later update/edit via the PAA, or an editor to change the layout (e.g., to nest a tool under a menu, and the menu in a toolbox...the PAA UI seems to only allow buttons or menus under menus).

Here are screen shots of the nesting/layout edit i am trying to describe:

And here's a sample of the config.xml edit i am trying to describe:

<ESRI.Configuration xmlns="http://schemas.esri.com/Desktop/AddIns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<Name>MouseClickTools</Name>
<AddInID>{bd14488e-47a2-4ab4-89d1-45aa9a8ef0d2}</AddInID>
<Description>Mouse Click Tools</Description>
<Version>0.1</Version>
<Image />
<Author>Author</Author>
<Company>Company</Company>
<Date>06/04/2014</Date>
<Targets>
    <Target name="Desktop" version="10.2" />
</Targets>
<AddIn language="PYTHON" library="MouseClick2_addin.py" namespace="MouseClick2_addin">
    <ArcMap>
        <Commands>
            <Tool caption="Window Click Tool" category="MouseClick" class="McToolClass_Win" id="MouseClick_addin.mcToolWin" image="Images\3DAnalystInterpolatePoint16.png" message="Click in Data Frame to see window coordinates." tip="Shows window coordinates."><Help heading="Windows Click Tool">Windows Click Tool</Help></Tool> <!-- 1st tool, defined -->
            <Tool caption="Map Click Tool" category="MouseClick" class="McToolClass_Map" id="MouseClick_addin.mcToolMap" image="Images\3DAnalystInterpolatePoint16.png" message="Click in Data Frame to see map coordinates." tip="Shows map coordinates."><Help heading="Map Click Tool">Map Click Tool</Help></Tool> <!-- 2nd tool, defined -->
        </Commands>
        <Toolbars>
            <Toolbar caption="Click Tools" category="MouseClick" id="MouseClick_addin.mcToolbar" showInitially="true"> <!-- 1st toolbar, defined -->
                <Items>
                    <Menu refID="MouseClick_addin.mcMenu" /> <!-- 1st menu nested in toolbar-->
                    <Menu refID="MouseClick_addin.mcMenu" /> <!-- 1st menu, added a 2nd time, just for layout editing illustration -->
                </Items>
            </Toolbar>
        </Toolbars>
        <Menus>
            <Menu caption="Click Clickity Click" category="MouseClick" id="MouseClick_addin.mcMenu" isRootMenu="true" isShortcutMenu="false" separator="true"> <!-- 1st menu, defined -->
                <Items>
                    <Tool refID="MouseClick_addin.mcToolWin" /> <!-- 1st tool, nested in menu-->
                    <Tool refID="MouseClick_addin.mcToolMap" /> <!-- 2nd tool, nested in menu -->
                </Items>
            </Menu>
        </Menus>
    </ArcMap>
</AddIn>