There is a prestigious location resource that generates influence when you claim it, there are also a few high level buildings that generate influence and sometimes you can get it as a quest reward.

I think there are also champion attributes that generate influence.

Having played a game recently to specifically keep an eye out for it,  I noticed the low level rat quest will allow you to get a one time gift of 20 influence or you can take a weapon or some gold.  This would allow you to build one building requiring influence if memory serves.

I remember being able to buy influence in Elemental, so I imagine you can part with gildar for some if one of the other AI's have it.  That is if you want to be nice to that particular AI.  Instead of just annexing it to your kingdom,  I mean.   

Also re: Almshouse is it really rare?  I mean every level 4 I've ever seen its been a choice.  There should be more choices to label things as common, uncommon, rare.  Or perhaps its not generating a new random number and always giving the same choices.. (shrug).    

The main source of Influence is Prestigious Locations.

I am just wanting to try out hiring mercenaries.

I think its buildings that creat zone controll that expand influnce also it seems as your building expand towards borders then borders expand