In countries in the civil law legal tradition (not just Europe but also most of Africa, Asia and Latin America), as opposed to the common law legal tradition of England, the "payment system" aspect of banking is generally handled primarily by the postal service and involves "push" transactions (the European name for them is giros) that are the moral equivalent of a money order as opposed to checks in the common law tradition which "pull" money out of a bank account whose balance is confirmed when the check is presented by the recipient for payment rather than when the instrument is issued the way that a money order would be.
We have private money transfer systems in the U.S. that operate more or less the way that a European postal account system does, the most famous being Western Union. Debit cards are also conceptually like European postal account systems because the available balance is confirmed before the payment is made and involves a reduction of a positive balance, rather than an increase of a negative balance the way that a credit card does. For larger transactions, wire transfers via banks are the norm, but wire transfers unlike loans and check transactions, are not functionally extensions of credit to the customer.
In both the postal systems and in private money transfer systems, there is usually some sort of fee charged to finance the operation, which is some combination of a monthly account fee, a flat per transaction fee, and a fee that is a function of the amount of the transaction.
A related line of business common in developing and third-world countries is that of a money courier, who physically delivers cash in person from a sender to a buyer for a fee, usually as an independent business person. Often money couriers network with each other so that a U.S. courier might deliver funds from an Algerian courier in exchange for the Algerian courier delivering from bound for Algeria by the U.S. courier. The two couriers would trade their obligations with each other rather than the physical cash originally delivered to them. This is basically a primitive form of wire transfer.
A slightly more sophisticated version of the same thing is called correspondent banking where someone sets up the moral equivalent of a no interest checking account in several countries and then handles transfers between the accounts.
The business of exchanging one currency for another that doesn't involve explicit interest is sometimes handled by stand alone businesses but is also commonly handled by commercial banks and could continue to be handled by them.
Another major activity of banks in the early days of banking was a form of secured lending called "factoring". In a factoring transaction, the bank buys accounts receivable from a business in exchange for cash, and the business then uses cash to make purchases. As payments on the factored accounts receivable are received, they are paid over to the bank.
The bank pays less than dollar for dollar for the accounts receivable based upon the past history of the business in successfully getting paid by those who owe it money plus an additional profit margin. But, unlike interest, this is a one time transaction that is not dependent upon how long it takes the bank to receive the accounts receivable, and it is generally structured to be non-recourse (i.e. if the bank isn't repaid its cash advance in full that is its tough luck).
What you and I ordinarily think of as a "bank" is what is called "commercial banking." There is a kindred finance industry called "investment banking" which lines up long term investments in the stock and bonds of publicly held companies for companies that want to go public or are already publicly held in a process called an "Initial Public Offering" (as distinguished from a secondary sale of a stock or bond from a party other than the issuing company), for a significant fee that is financed with the public offering proceeds.
If interest were disallowed or greatly limited, big business would get more of its financing from stock, preferred stock (which is a debt-equity hybrid), and would probably limit debt transactions to "money market" transactions in which big businesses borrow cash at very low interest rates for short periods of time (which even restrictive usury laws might permit) basically for working capital purposes.
Trust Management, Safe Deposit Boxes and Cash Management
Most banking functions are structured as credit transactions (even deposit accounts are currently merely loans from the customer to the bank). But, not all.
Some banks have trust departments that manage money held in trust for others (both conventional private trust funds, usually for family members, and also charitable trusts and accounts such as retirement funds and security deposit funds and monies held in trust by lawyers for their clients), typically on a fee basis that is a function of the amount of assets under management. These can sometimes be invested in real world investments like real estate or leased equipment, as well as stocks and bank deposits.
Banks also customarily operate safe deposit boxes and there is no reason that some institution or other wouldn't continue to offer this service.
Cash management is what armored car drivers, sometimes affiliated with banks and sometimes as independent businesses do. They drive around, pick up cash received from businesses (and drop off new cash for day to day operations), and get it counted and credited to the account of a business in a manner that is conscious of robbery and embezzlement risks. (This is a booming industry in the era of the all cash legal marijuana industry these days.)
Another variation on this involves precious metal depositories and warehouses (including grain silos). In these cases, an institution stores commodities such as precious metals, grains, oil, goods in shipping container, etc. in exchange for transferrable warehouse receipts or similar pieces of paper. Rather than physically transferring 4 ounces of gold to pay for something, for example, you might transfer a receipt for 4 ounces of gold.
Just because private lenders wouldn't be allowed to charge interest doesn't mean that governments couldn't issue interest bearing bonds (municipal bonds or treasury bonds in current parlance). Indeed, they might even be legal for private parties since these interest rates are typically very low because default rates are very low.
Buying government bonds creates a stream of payments in the future. One could trade in government bonds at discounts and premiums as the case might be in order to pre-pay obligations that would otherwise accrue over a period of installments, while receiving some time value of money benefits. This would be indirect interest, but might be allowed if government bonds were exempted.
This is a method used now to close out loans in cases where prepayment is prohibited or prepayment incurs a significant penalty, while avoiding any meaningful risk of default because government bonds almost never default.
For example, government bonds might be paired with lease to own transactions to discount future payments and close out the deals.
Various kinds of bankers and brokers arrange these deals now and private banks might continue to do so.
Credit Unions and Mutual Banks
The New Deal featured many cooperatives, especially in rural areas, which are businesses owned by someone with a relationship other than as an investor in the business. For example, a mutual insurance company is one owned by its policyholders.
Prior to the FDIC, mutual banks (owned by depositors) and credit unions (non-profit banks) were very popular because they were much less prone to taking risky high levels of leverage to benefit the private investors and frequently went bankrupt in recessions causing the loss of bank deposits. In contrast, mutual banks and credit unions, acting in their owner's interests, were much more conservative and rarely went bankrupt even in recessions (often called "panics" at the time). If the FDIC had not been created, a ban on private investor owned banks, but not mutual banks and credit unions might very well have been allowed, and because any excess profits from these institutions benefit account holders, there would be (and is today) little incentive for them to unnecessarily jack up fees or charge unreasonably high interest rates.
Non-Bank Credit, Bonding and Letters of Credit
You would also expect to see in an economy without significant interest being allowed, an expansion of "trade credit" between vendors and purchasers (e.g. selling goods that only have to be paid for in 30 days), and a replacement of financing transactions with lease to own transactions (now commonly seen in auto financing mostly because it affords business users of leased vehicles more level deductions for tax purposes).
Private banks might get into this trade credit economy by offering "bonding services" for private companies. A bonding agreement in this context means that a financial institution such as a bank would promise to pay any lawful debts of the party to which trade credit was extended up to a dollar cap in exchange for a fee. Basically the bank is co-signing your loans. These arrangements are now pretty much restricted to government officials guaranteeing that their services will be lawfully performed and for firms in the construction trades, but the concept would be more widely used if credit from banks for working capital was not as easily available. A subtype of this transaction is mortgage insurance, but bonding is usually what it is called in cases of domestic trade credit and contractual liability guarantees.
Letters of credit issues for a fee are a variation on bonding (where the bank actually pays all debts rather than just defaulted ones in the transaction) that are uncommon now except in international transactions but might become common if interest bearing loans were prohibited.
You might also see lots of loan sharking and other black market credit transactions.