penso che dovresti innanzitutto vedere se riesci a far riconoscere il modem usb a linux, guarda che chipset ha, se è supportato (magari conexant, alcatel ecc.) hai buone possibità, altrimenti mi sa che devi comprarti un router
se riesci a far andare il modem penso che tu possa gestire benissimo il nat con linux, però aspetta che arrivi qualcuno più competente (io ho fatto una ricerchina tempo fa ma non ho approfondito troppo) che ti dia una conferma