Custom Header Complete with different Navigation

Hello,

I need your ideas on how to achieve the following.

A custom header with a custom Navigation for different categories and their posts.

For example, I have a personal finance blog and the main navigation has the following Menu:

Home | Taxes | loans | Insurance

taxes, loans, insurance are categories.

Now when I am viewing the Loans Category, it has it's child categories and the navigation menu should be:

Home | Personal loans | Bank loans | etc...

This should be the same for posts under these "loans" categories.

When I move to the other categories I get a different menu.

Can this be done, I know there is a plugin (conditional menus) but it does not let me achieve this.
and I think a Custom Header will work but I am not sure if the navigation can be different.

What do you think?

Thanks