Fastest way to add custom category attribute to frontend menu category tree model

The simplest way to add this attribute is use XML.
This sample part of code displayed below, should be inserted in Your own module in config.xml file

<frontend>
<category>
<collection>
<attributes>
<custom_attribute_code/>
</attributes>
</collection>
</category>
</frontend>

After that You can use this attribute, in rendering method _renderCategoryMenuItemHtml defined in Mage_Catalog_Block_Navigation.
Like that:

$category->getCustomAttributeCode()

Please remember to rewrite this class, or at least move it to app/code/local/.. directory.