Is CBSubs the solution for me?
Certainly, CBSubs allows for a selection of different durations of subscriptions as well as custom pricing.
Is there an Australian Gateway? I ask becasue I wonder what would happen if the payment went through the US?
Don't know about Australian specific gateway, but PayPal can certainly meet those needs. More on gateways and CBSubs in general can be found at the below link.
www.joomlapolis.com/cb-solutions/cbsubs
Do you know what the gateways charge per transaction?
Believe PayPal is 3%, but can't recall if this has changed or what the charge rate is Australia. You'd need to check the supported gateways sites directly to review their rates.
This is a not for profit organisation so we don't want to loose to much money in transactions.
Rough estimate you're looking at maybe losing $1 per transaction, but you should check the supported gateways and do the math directly. Some may have zero fees for certain transactions. Believe PayPal has a not for profit account that you can register for with lower fees, but you'll need to see PayPals sites for further details.