There are 2 ways to do it. You will need test where is your header navigation content coming from.
For instance, in Magento 1.9.2.2 the content comes from: app/design/frontend/rwd/default/template/page/html/topmenu/renderer.phtml
First Approach
In this file make the below modifications to FOREACH loop ONLY:
foreach ($children as $child) {
$child->setLevel($childLevel);
$child->setIsFirst($counter == 1);
$child->setIsLast($counter == $childrenCount);
$child->setPositionClass($itemPositionClassPrefix . $counter);
$outermostClassCode = 'level'. $childLevel;
$_hasChildren = ($child->hasChildren()) ? 'has-children' : '';
$html .= '<ul><li '. $this->_getRenderedMenuItemAttributes($child) .'>';
$html .= '<a href="'. $child->getUrl() .'" class="'. $outermostClassCode .' '. $_hasChildren .'">'. $this->escapeHtml($this->__($child->getName())) .'</a>';
if (!empty($childrenWrapClass)) {
$html .= '<div class="'. $childrenWrapClass .'">';
}
$nextChildLevel = $childLevel + 1;
if (!empty($childrenWrapClass)) {
$html .= '</div>';
}
$html .= '</li></ul>';
if (!empty($_hasChildren)) {
//$html .= '<ul class="level'. $childLevel .'">';
//$html .= '<li class="level'. $nextChildLevel .' view-all">';
//$html .= '<a class="level'. $nextChildLevel .'" href="'. $child->getUrl() .'">';
//$html .= $this->__('View All') . ' ' . $this->escapeHtml($this->__($child->getName()));
//$html .= '</a>';
//$html .= '</li>';
$html .= $this->render($child, $childrenWrapClass);
//$html .= '</ul>';
}
$counter++;
}
Next is to navigate to app/design/frontend/rwd/default/template/page/html/topmenu/renderer.phtml
:
<nav id="nav">
<?php /*<ol class="nav-primary">*/ ?>
<?php echo $_menu ?>
<?php /*</ol>*/ ?>
</nav>
The above way you will be able to display each of your categories as required.
Second Approach
if your code comes from this file: app/code/core/Mage/Page/Block/Html/Topmenu.php
You will need to override this file: app/code/core/Mage/Page/Block/Html/Topmenu.php
Create the below files:
app/code/local/Namespace/Page/Block/Html/Topmenu.php
app/code/local/Namespace/Page/etc/config.xml
app/etc/modules/Namespace_Page.xml
Hoping you know what needs to go into which file.
Inside Topmenu.php, copy paste below function:
/**
* Recursively generates top menu html from data that is specified in $menuTree
*
* @param Varien_Data_Tree_Node $menuTree
* @param string $childrenWrapClass
* @return string
* @deprecated since 1.8.2.0 use child block catalog.topnav.renderer instead
*/
protected function _getHtml(Varien_Data_Tree_Node $menuTree, $childrenWrapClass)
{
$html = '';
$children = $menuTree->getChildren();
$parentLevel = $menuTree->getLevel();
$childLevel = is_null($parentLevel) ? 0 : $parentLevel + 1;
$counter = 1;
$childrenCount = $children->count();
$parentPositionClass = $menuTree->getPositionClass();
$itemPositionClassPrefix = $parentPositionClass ? $parentPositionClass . '-' : 'nav-';
foreach ($children as $child) {
$child->setLevel($childLevel);
$child->setIsFirst($counter == 1);
$child->setIsLast($counter == $childrenCount);
$child->setPositionClass($itemPositionClassPrefix . $counter);
$outermostClassCode = '';
$outermostClass = $menuTree->getOutermostClass();
if ($childLevel == 0 && $outermostClass) {
$outermostClassCode = ' class="' . $outermostClass . '" ';
$child->setClass($outermostClass);
}
$html .= '<ul><li ' . $this->_getRenderedMenuItemAttributes($child) . '>';
$html .= '<a href="' . $child->getUrl() . '" ' . $outermostClassCode . '><span>'
. $this->escapeHtml($child->getName()) . '</span></a>';
if ($child->hasChildren()) {
if (!empty($childrenWrapClass)) {
$html .= '<div class="' . $childrenWrapClass . '">';
}
//$html .= '<ul class="level' . $childLevel . '">';
$html .= $this->_getHtml($child, $childrenWrapClass);
//$html .= '</ul>';
if (!empty($childrenWrapClass)) {
$html .= '</div>';
}
}
$html .= '</li></ul>';
$counter++;
}
return $html;
}

Let me know if this helps.
Happy Coding...