How can I output child urls that reflect a structured menu hierarchy when the structure has no URL format specified?
Craft can't really produce the uri patterns/routes you need automatically without giving it something to work with. With that said there are a couple of ways to approach this.

1) One option is to simply make your pages section into a structure; creating the needed hierarchy elements, and use it directly to generate your navigation. You may also want to specify additional 'entryType(s)' for header items, etc (i.e. items that don't have a corresponding page and/or are used exclusively for creating the nested route structure or for navigation headers, buttons, etc). You can then test entry.type in your template and deny or reroute the request accordingly.

2) Another option is to define a url format for your nav structure, which represents the uri pattern(s) that you would like to have (i.e. if the structure represents the site root then set the uri to {slug} and children to {parent.uri}/{slug}).

Using this approach, you would want to set up a template for your navigation structure which essentially includes the corresponding page template, as needed.

Something like this perhaps:

{% if entry is defined %}
    {% set relatedPage = entry.contentLink.first %}
    {% type = relatedPage.type %}
    {% include ["pages/_types/" ~ type, "pages/_types/default"] with { 'entry': relatedPage } %}
{% else %}
    {% redirect '404' %}
{% endif %}


Notice that when including the page template, we are redefining the entry variable to be the related page, so that the 'page' template doesn't have to worry about it, and can be loaded directly or via the navigation template as needed. 

Note: you may want to disable urls for your pages channel if you don't ever want users to access pages through those routes.