So I found the solution to my own problem, had to do it "the hard way" since this functionality hasn't been supported yet.

Basically I intercepted the postMixInProperties event of the PageNavigationTree. In that event I got the context menu commands by using the _contextMenuCommandProvider, reordered these commands, and set the new value back, still by using the _contextMenuCommandProvider. The result looks like this:

We need a module initializer to be able to do this, go to this page if you haven't configured one. Here's my module initializer for the POC:

define([
    "dojo",
    "dojo/_base/declare",
    'dojo/_base/array',
    "epi/_Module",
    "epi-cms/plugin-area/navigation-tree",
    "alloy/Command/CustomCommand",
    'epi-cms/component/PageNavigationTree',
    'epi-cms/command/NewContent'
], function (dojo,
    declare,
    array,
    _Module,
    navigationTreePluginArea,
    CustomCommand,
    PageNavigationTree,
    NewContentCommand
) {
    return declare("alloy.moduleInitializer", [_Module], {
        initialize: function () {
            this.inherited(arguments);

            // Do any custom module initialization here

            // Add Custom Command button to the Navigation Tree
            navigationTreePluginArea.add(CustomCommand);

            // Customize PageNavigationTree
            var originalPostMixInProperties = PageNavigationTree.prototype.postMixInProperties;
            // Extends the original postMixInProperties
            PageNavigationTree.prototype.postMixInProperties = function () {
                // call the original function
                originalPostMixInProperties.apply(this, arguments);

                //getting the context menu commands
                var customCommands = this._contextMenuCommandProvider.get("commands");

                // updating the style, since I wanted to group My Custom Command with the New Page command, so I updated New Page command to a normal menu item style, and I updated My Custom Command to a menu item with a separator.
                var customCmdIndex = 0;
                var newContentCmdIndex = 0;
                array.forEach(customCommands,
                    function (command, i) {
                        if (command instanceof NewContentCommand) {
                            newContentCmdIndex = i;
                            command.category = 'context';
                        } else if (command instanceof CustomCommand) {
                            customCmdIndex = i;
                            command.category = 'menuWithSeparator';
                        }
                    });

                // moving My Custom Command to right under the New Page Command
                customCommands.splice(newContentCmdIndex + 1, 0, customCommands.splice(customCmdIndex, 1)[0]);

                this._contextMenuCommandProvider.set("commands", customCommands);
            };
        }
    });
});