How can I assign an application to all desktops using the keyboard?
Here's a solution that does use GUI scripting:

In Automator, create a Service. Use the 'Run AppleScript' action, with the AppleScript below. Then, in Services Preferences, you can assign a keyboard shortcut to the service.

on run
    -- get active application
    tell application "System Events" to set activeApp to name of first application process whose frontmost is true

    -- right click that application in the dock
    tell application "System Events" to tell UI element activeApp of list 1 of process "Dock"
        perform action "AXShowMenu"
        click menu item "Options" of menu 1

        -- is it currently checked?
        set isChecked to value of attribute "AXMenuItemMarkChar" of menu item "All Desktops" of menu 1 of menu item "Options" of menu 1 as string

        -- toggle between "None" and "All Desktops"
        if (isChecked = "✓") then
            perform action "AXShowMenu"
            click menu item "Options" of menu 1
            click menu item "None" of menu 1 of menu item "Options" of menu 1
        else
            perform action "AXShowMenu"
            click menu item "Options" of menu 1
            click menu item "All Desktops" of menu 1 of menu item "Options" of menu 1
        end if

    end tell
end run


Potential caveats:


It's slow
It briefly flashes the dock options menu
It will stop working if the UI changes
Sometimes (but very inconsistently, not all the time), I'm prompted to allow either the current application OR Automator to control the computer. I haven't done that and it still usually works.