Is there an on the fly service to exchange physical currency for BTC for payment processing? I want, as a merchant, to receive money from my customers in the form of
bitcoins, to avoid the 2~4% fees. But many of my customers don't have
BitCoins. I was wondering if there is a service that would allow for a customer to
spend X amount of USD (or any other currency) to buy the corresponding
amount of BTC "on the fly", without requiring customers to have BitCoins or
even a BTC wallet.

Is there such a service?
I don't know of any third parties that provide this service. I do know of a few (Example) that provide the opposite, where a customer has bitcoin, but the merchant will not accept it, however.

The problem here is that these customers (in your scenario) would be giving a credit card for payment. They have up to 30 days to claim the charges are fraudulent and unless you have some good proof that they are not, you will not get your money from them. In your example, they would be buying bitcoin with it, which would then be transferred to you, leaving this third party carrying all the risk. The only way I, personally, would run a business like this is with high fees to offset the high risk. You might at well just raise prices 2~4%. It's easier and is becoming more common for brick and mortar shops to do this for card purchases and not cash.

The difference with the reverse situation, where the customer has bitcoin and the merchant will not accept it, is that there is very little risk. The customer is buying money with the bitcoin and once the bitcoin transaction is verified it is permanent.