I like the idea about killing xenos! move your sair cruiser to liberty and tell the navy "I AM HERE TO KEEL XENOS! OLOL"
or better yet! take your sair cruiser on some GMG missions!
[/silly]
but yeah, only real suggestion I have is try for a bribe. but I've noticed raising BHG rep on my BHG char somehow lowers zoner rep, try killing some bunter npcs.
but the xeno idea does hold merit, as long as you can make you way to the systems between liberty and anywhere else, but unfortunately xenos are not hostile with sairs, so the political REAG might be extreme when someone sees you with 500 xeno pilots in your hold. but that wont stop me! LOOK OUT XENO NPCS!