So you have pre-compiled code that you're linking into your Arduino project? This is the only instance in which you cannot change the pins (easily). In all other cases - it can be done.
Instead of making things hard on yourself by having to resort to things like SoftSerial which may or may not work reliably, why not tell a bit more about this mystery application that blocks pins 20 & 21? Perhaps there's a way around this.