Lets say I make the next google ads service (hypothetically speaking), how can I pay my users in more or less real time? with minimal or no additional cost to the company.
You can't. Not both in real-time and for (near) free.
Distributing payments always has a cost. This is part of the reason why micropayments still aren't doing much (the processing costs as much as the payment) and why there is a billion dollar merchant services industry.
The most common approach is for you to keep account of your users earnings in a DB. Once those amounts are high enough, then you could do a Paypal to Paypal transfer. This can be done via API, and costs you very little, (just a transaction amount).
For countries where they cannot "withdraw to local bank" then your options are payment debit cards such as payoneer.
If your users are just in the US, then I would avoid payoneer because their rates are expensive. in that Scenario you could still offer debit card payments. I think the pricing is $5 per card, flat (thats the best i have found). You still would have an expense of loading the cards, this is done through ACH, and costs again only for the transaction amount.
Make sure that you require 1099 from those getting paid.
I think fees will be the least of your worries. Fraud is what will cost you. If you pay in real time, fraudsters will work you over before you realize you have been taken. A grace period gives you a little time to weed out the ne'er-do-wells.
The lowest fees are for ACH (Automated Clearing House) credit (meaning from your biz account to clients account) transactions. Also you can have service where the payment processing company will tear paper checks for your for monthly fee.
paymentsgateway.net - is one of the ACH credit processors. Check out their fees page.
Amazon Payments allows sending money but not via API yet. They have a lot lower fees than PayPal.
BTW, you would need to hire developer to integrate API for the ACH on your site.
Also PayPals new Adaptive API allows for specification of who will pay the fees.