Bottom line: it's of no advantage to Bank A to allow you to do this (at least, without charging a fee).
As Fattie points out in comments, another potential issue is Bank A not knowing any details of Bob's account with Bank B. At least in the UK, there are – at least in principle – ways around this, although I don't know whether any of these ways currently (or ever) existed in the US. I'll come back to this point later.
(The rest of this answer is biased towards the way UK banks operated. The actual practices in the US may not be, or may never have been, the same, but underlying principle – who's going to pay – should carry over.)
Who Pays for the Paperwork?
Up until relatively recently, banking practices all revolved around movement of paper. If Bob (Bank B) receives a cheque from Alice (Bank A), let's consider some of the scenarios and (in simplified terms) what must happen to various bits of paper:
Bob pays it in (deposits it) at his own branch of Bank B. They can make an immediate record against his account (as uncleared funds) and will then send the cheque, via their head office, to Bank A. They will check the balance of Alice's account and accept or decline the cheque accordingly. In "old times", the decision to honour or not the cheque would be made by Alice's branch with Bank A, once the cheque had been sent to them from Bank A's head office.
Bob pays it in at a different branch of Bank B than his own. Essentially the same process as (1). In "old times" a record of Bob's uncleared funds would take longer to appear as account balances would have been held locally.
In both cases, "moving bits of paper" costs money. Bank B's costs would either be taken from Bob directly in the form of fees applied to his account, or indirectly through the "opportunity cost" Bank B makes from having Bob as a customer. Bank A's costs would be taken from Alice in the same way.
Bob presents the cheque for cashing at Alice's branch with Bank A. They would be able to tell immediately whether Alice has sufficient funds to honour the cheque, and will hand over the cash if she does. (Subject to Bob passing whatever identity checks they may want, or be forced, to make).
Bob presents cashes the cheque at a different branch of Bank A. These days the process would be the same. In "old times", when balances were held at branch level, they would either refuse to cash it or would have to manually "clear" the cheque (i.e. phone Alice's branch and ask if there are sufficient funds). There would be undoubtedly be an additional fee (payable on the spot by Bob) for doing this.
In these two cases, only Bank A has to "move paper". As before, Alice would either be charged a fee directly, or indirectly from the money the bank makes from having her as a customer.
- Bob wants to pay the cheque in at any branch of Bank A. Assuming they have Bob's account details with Bank B (see below), as well as checking whether Alice had sufficient funds they would then have to send appropriate paperwork to Bank B so that they could credit Bob's account.
For their "internal" paperwork, Bank A can charge Alice as in (3,4) above. However, who's going to cover the extra cost of sending the paperwork to Bank B? They would either need some arrangement with Bank B to pay their costs (who would later pass them on to Bob) or they would have to charge Bob an immediate fee for depositing the cheque.
For completeness, there is also:
- Bob wants to pay the cheque in at any branch of Bank C (that has no connection with either Alice or Bob). In theory this could be possible, as the "paper transport channels" are in place... Bank C would have to send the cheque to Bank A and the credit-slip/BGC (see below) to Bank B.
Because Bank C has no relation to either party, this would be exceedingly unlikely to happen, unless there was some prior arrangement between banks to allow this (as mhoran_psprep's answer suggests can happen with some Credit Unions). I believe such arrangements have occasionally happened in the past between certain pairs of banks, and currently the UK's Post Office (vaguely equivalent to US Mail/USPS) have arrangements with many UK banks to provide everyday banking services (see Everyday Banking).
Paying-in Slips and Bank Giro Credits
In all cases (except cashing the cheque) the bank that Bob visits will need to record his account details. In the UK, at least, this was done by filling in a paying-in slip or a Bank Giro Credit form with the amount of cash and/or cheques that you were paying-in, and the date.
Most (UK) cheque books would have a few of these at the back, pre-printed with the account-holder's details. You could also get a book of personalised paying-in slips. Alternatively, bank branches would have a stock of "blank" slips on the counter. If you used one of these, as well as filling-in the amount and date, you would need to enter your account details.
For all of my memory (back to the mid-70s), using these was free (at least for personal customers) when paying into your own account at your own branch of your bank, and probably free if you paid in at a different branch of your bank (cases (1,2)).
If either cases (5,6) were ever possible, a BGC would be sufficient for the receiving bank to know where to send the details of the deposit. My recollection is that it didn't make a difference that you happened to be paying in a cheque drawn on the bank where you were paying-in (case 5): all that mattered was that you wanted to pay-in through a bank that wasn't your own. For the reason stated above (who's going to pay), I'm not aware of this being possible unless there was a prior arrangement between the banks concerned.
Third-Party Bills
As described on the BGC page linked above, bills from many companies and credit-card statements would come with a detachable BGC printed at the bottom. You could post this back (with a cheque) or pay the bill with cash and/or a cheque at a bank or Post Office.
This certainly wouldn't cost you anything if you used your own bank (essentially the same as case (5) above, but where Alice is presenting the paperwork) or at the Post Office. If you wanted to use a different bank, they may decline or charge a fee.
The Modern Day
Most of this answer has been from a historical perspective, dealing with pieces of paper. Although technology has moved on, processing deposits still costs money, and banks aren't going to do it for free.
For some years some ATMs allow you to pay-in cash and/or cheques, although in my (UK) experience, the same principal holds. Even though cash withdrawals from bank-owned ATM's are (at the time of writing) free for everyone (whoever they bank with), I can only use an ATM owned by my bank to pay in.