Removing the UL bit is going to break your code, you will end up with invalid code (see w3c validation), this means you will get all sorts of crazy things happening (if you didn't remove the closing ul tag), you will also have li elements not surrounded by a ul parent element, so this my cause errors in how it looks across different browsers too......
The menu system works on a automatic creation system, where by the links are dynamically created, if you want to do something like
hello | another | footer | link
then you will need to hack the core code, as this type of layouts is more destined for static layouts. You could just remove the footer navigation and change the copyright footer in the settings manager to contain the links you want, but then this sort of defeats the abject of having a cms that auto generates menus.
To be completely honest those little | do not really solve any purpose do they, do you really need them, what purpose do they serve??.
If you want to do these changes you will need to alter the core code, plus you need to remember that when updates come through for new releases, you will need to track your changes if you wish to upgrade (or your changes will get lost), if your not proficient in php I would not recommend making changes to core code, but hey it's your bag so you are free to do as you wish.
I can't really find the time at the mo, as I am bogged down with a lot, including the next version, your requests will need changes to be made, and they will not be completely straightforward either (as the side bar and nav use same code, but you want them to display differently).
My best answer, use css to style links, not html (using >> or |), use css styling like borders, bullets, bullet images etc, this is the correct way to style (not by adding extra characters), and this way would be supported by future upgrades of core
just my 2 pence