So, your only choices is to lower SoftSerial baudrate, or forget about Uno.
There are plenty of other hardware choices, not only Mega2560.
You can use MapleMini clones, they use the STM32F103 which has 3x hardware serial, 2x I2C, 2x SPI and direct USB.
Those are also well supported under ArduinoIDE (http://stm32duino.com)