No. Frodo's ability is a Fellowship action, so can only be triggered in the Fellowship Phase (not when you are playing starting companions). If the text just said "Each time you play a Ring-bound companion you may remove a burden," then yes, but because it says "Fellowship:," it's an action so must be done in the correct phase.