This might work as-is with no firewall changes (except perhaps permitting http and https Internet access for the static IP addresses of the machines running LogMeIn).
Firewalls that are configured securely do not permit inbound connections that originate from outside the firewall. The way LogMeIn works is that the LogMeIn client that's installed on the internal PCs initate an outbound connection to the LogMeIn servers (the broker) over https. Given that it's https (or http) this traffic is indistinguishable from normal web browsing. When the external user goes to the LogMeIn web site to connect to an internal PC, the external user rides the https connection that was initiated by the inside client. Since the inside client initiated the connection, all is good.
Like I said above, you may need to have your firewall person add the addresses of the inside PCs to the firewall, but again it's all over https and looks like web traffic.
Prior to any changes I'd test from a PC that already has Internet access and see what you get.
Update: This support article on the LogMeIn web site seems to confirm the above. https://logmeinsupport.com/kblive/crm/selfservice/displaywh.jsp?DocId=8208&SecMode=1. It does make a good point that if there's a firewall (Windows firewall or other) on the internal PCs you may need to grant access to the LogMeIn executables, however this is unrelated to the network firewall piece.
Hope this helps.