It is not at all impossible and you should complain to the Warband/M&B Devs if you are unhappy - that is not our doing. All you need do is wait until you have improved your relations with that faction - you can pay a lord to do that for you. Also you can help out lords of a faction and gain + relations that way. Or, wait until you are levelled up enough to handle what the gate guards throw at you.
This is covered in the general Warband info and is not really a PoP topic, so I am locking it.