How to run two Messenger applications logged into different accounts?
Yes, at the very least that will have to be done. You may also have to re-sign the apk, and also change any absolute references to the Application context inside the java code and/or machine code. This will require lots of effort, you might as well build your own Messenger interface via Facebook's API. Facebook does have a developer API for this kind of stuff, you may want to look into that.

Facebook Developer SDK

I would try renaming the package first, without even decompiling anything, if it crashes due to internal package pointers, I would probably try to build a plug-in.

Hope that helps,