I managed to change my custom module to use the Magento new way as recommended with the patch 6788. So I give here as a reference for other.

1. Change to router in the config.xml file:

Before:

<admin>
    <routers>
        <adminhello>
            <use>admin</use>
            <args>
                <module>Pulsestorm_Adminhello</module>
                <frontName>admin_adminhello</frontName>
            </args>
        </adminhello>
    </routers>
</admin>

After

<admin>
    <routers>
        <adminhtml>
            <args>
                <modules>
                    <adminhello before="Mage_Adminhtml">Pulsestorm_Adminhello_Adminhtml</adminhello>
                </modules>
            </args>
        </adminhtml>
    </routers>
</admin>

2. Change to the Controller

2.1.

Before Path

/app/code/local/Pulsestorm/Adminhello/controllers/Adminhtml/AdminhellobackendController.php

After path

/app/code/local/Pulsestorm/Adminhello/controllers/Adminhtml/Adminhello/AdminhellobackendController.php

2.2

Before class

class Pulsestorm_Adminhello_Adminhtml_AdminhellobackendController extends Mage_Adminhtml_Controller_Action 
{
..
}

After class

class Pulsestorm_Adminhello_Adminhtml_Adminhello_AdminhellobackendController extends Mage_Adminhtml_Controller_Action
{
...
}

3. If you have an adminhtml.xml file (just give as an example as below)

Before

<config>
    <menu>
        <adminhello_config translate="title" module="adminhello">
            <title>Adminhello Settings</title>
            <sort_order>100</sort_order>
            <children>
                <list_action translate="title" module="adminhello">
                    <title>Manage Hellos</title>
                    <sort_order>4</sort_order>
                <action>adminhello/adminhtml_adminhellobackend</action>
                </list_action>
...
            </children>
        </adminhello_config>
    </menu>
</config>

After

<?xml version="1.0" encoding="UTF-8"?>
<config>
    <menu>
        <adminhello_config translate="title" module="adminhello">
            <title>Adminhello Settings</title>
            <sort_order>100</sort_order>
            <children>
                <list_action translate="title" module="adminhello">
                    <title>Manage Hellos</title>
                    <sort_order>4</sort_order>
                <action>adminhtml/adminhello_adminhellobackend</action>
                </list_action>
...
            </children>
        </adminhello_config>
    </menu>
</config>

4. Change in your codes

Before: getting URLs

Mage::getUrl('adminhello/adminhtml_adminhellobackend/doSomething')

After: getting URLs

Mage::getUrl('adminhtml/adminhello_adminhellobackend/doSomething')

5. Change in layout files (if you have layout files, for example as below)

Before layout

<adminhello_adminhtml_adminhellobackend_index>
...
</adminhello_adminhtml_adminhellobackend_index>

After layout

<adminhtml_adminhello_adminhellobackend_index>
...
</adminhtml_adminhello_adminhellobackend_index>