This may just be a shot in the dark but you may find my argument reasonable.
First a discussion on ilal ish-shara'i, or "bases of rules."
My understanding of prohibition of riba is that its due to the act of charging money without actually rendering an equivalent service to the customer or society.
There are a number of Shia hadiths that suggest this, in my opinion.
Two from Jafar us-Sadiq
[ ٢٣٢٧٧ ] ٨ ـ محمد بن علي بن الحسين بإسناده عن هشام بن الحكم أنه سأل
أبا عبدالله عليهالسلام عن علة تحريم الربا؟ فقال : انه لو كان الربا
حلالا لترك الناس التجارات وما يحتاجون إليه ، فحرم الله الربا لتنفر
الناس من الحرام إلى الحلال وإلى التجارات من البيع والشراء ، فيبقى ذلك
بينهم في القرض .
Hisham asked Aba Abd Allah about reason of prohibition of riba. He
said: Had usury been halal, people would have abandoned trades and
what they need...
[ ٢٣٢٧٨ ] ٩ ـ وبإسناده عن هشام بن سالم ، عن أبي عبدالله عليهالسلام
قال : إنما حرم الله الربا كيلا يمتنعوا من صنائع المعروف.
Aba Abd Allah said: Allah forbid riba so that people won't refrain
from praiseworthy industries. (source)
And one from Imam Ridha
[ ٢٣٢٨٠ ] ١١ ـ وبإسناده عن محمد بن سنان ان علي بن موسى الرضا
عليهالسلام كتب إليه فيما كتب من جواب مسائله : وعلة تحريم الربا لما
نهي الله عزّ وجلّ عنه ، ولما فيه من فساد الاموال ، لان الانسان إذا
اشترى الدرهم بالدرهمين ، كان ثمن الدرهم درهما وثمن الآخر باطلا ،
And the reason for prohibition of riba is due to ... corruption of
properties, since when man sells a dirham for two, the price of one
dirham is one, and the price of the other is void... (source)
What I deduce from the above hadiths, is that riba is made forbidden for its not in exchange for a real productive service to the individual or society.
This is why overpricing and tatfif (providing less than the price charged) is and gambling also prohibited in Islam. You earn without contribution to the person or society.
In layman's term, usury is earning without working. Thus, the usurer can enrich himself at the expense of others without making a positive contribution.
The modern response to that, though, is that interest is the time value of money, i.e. the usurer forgoes his right to use money for some time so he deserves the compensation.
But my response is that why a usurer actually does that instead of investing the money himself? It is obvious: for earning without the trouble of work and investment! In other words, the usurer puts the burden of work on some one else's shoulder expecting earnings. Obviously nobody forces the usurer to temporarily forego his right to use the money but he does that voluntarily for the advantage of earning without work!
Now some might still counter this argument by comparing riba to muzariba in Islamic commerce, in which a party advances capital to be invested by another party, expecting a share of return on the investment.
However there's an important component in muzariba that eliminates the possibility of undeserved profit: the parties will share in both profits and losses! So first of all there's no guaranteed and predetermined return. And then, since this introduces risks the creditor would have to advance something more than just providing capital, like he needs to find a competent business party, know about the state of the markets and then make sure the joint venture is successful which may require his oversight over the business process to its conclusion. All of these involvements are productive work, making the creditor worthy of profits from his credit!
Now apply this general wisdom to any contract to determine whether it is lawful. In case of exchanging coins with banknotes and vice versa, one might argue that the party providing the equivalent is not rendering any service. He is only exchanging a unit with its exact worth, so he is not doing an added work to expect a profit.
However, there's this general economic axiom that demand is an indicator of value. That is, there is generally a correlation between demand for something and its actual value. Of course, not all forms of demand are lawful and aiming at truly useful things (think of demand for haram food, alcohol , drugs, etc), but the fact remains that at least in the eye of the buyer, always, the object of demand has some use for him. So depending on your belief system, if the service or commodity is useful and legit, then the seller can expect a profit from exchanging it.
Now in case of exchanging units of currency, it is obvious that the demand is driven by a perceived use or value in the desired form of currency beyond its nominal value and in this case that would be the physical form of the currency that is desired and useful. Notes here are more valuable in terms of convenience in keeping and carrying them around. So the counter party may expect compensation from forgoing that practical value in notes for those awkward mass of coins that you want to hand him! Sounds fair, right?
So I'd venture to say that the deal is normally legit!
Wa Allahu A'lam...