As you said audiencing is not available with what you have. The only real option out of the box is the security trimming you mentioned. It is important to note that there are two kinds of links that will show up in the navigation. There are the objects that are shown, such as sub-sites or pages that are added (when it is configured to show those objects) and then there are the manual links that are added. Any manual link that is added is NOT security trimmed, and in fact SharePoint does not evaluate the url to validate if it is a SharePoint item or something in a non-SharePoint system.
The other alternative is to create your own navigation provider and data source. This would allow you to pull the data from anywhere including a SharePoint list or an XML file, and you then have the added benefit of controlling exactly how you want it to behave with relation to it being security trimmed, targeted to group membership, etc.