Your luck is in, this problem has been solved before (although not solely due to a scarcity of precious metals). Emphasis mine:
For he makes his money after this fashion. He makes them take of the
bark of a certain tree, in fact of the Mulberry Tree, the leaves of
which are the food of the silkworms,–these trees being so numerous
that whole districts are full of them. What they take is a certain
fine white bast or skin which lies between the wood of the tree and
the thick outer bark, and this they make into something resembling
sheets of paper, but black. When these sheets have been prepared they
are cut up into pieces of different sizes. The smallest of these sizes
is worth a half tornesel; the next, a little larger, one tornesel;
one, a little larger still, is worth half a silver groat of Venice;
another a whole groat; others yet two groats, five groats, and ten
groats. There is also a kind worth one Bezant of gold, and others of
three Bezants, and so up to ten. All these pieces of paper are [issued
with as much solemnity and authority as if they were of pure gold or
silver; and on every piece a variety of officials, whose duty it is,
have to write their names, and to put their seals. And when all is
prepared duly, the chief officer deputed by the Kaan smears the Seal
entrusted to him with vermilion, and impresses it on the paper, so
that the form of the Seal remains printed upon it in red; the Money is
then authentic. Any one forging it would be punished with death.] And
the Kaan causes every year to be made such a vast quantity of this
money, which costs him nothing, that it must equal in amount all the
treasure in the world.
With these pieces of paper, made as I have described, he causes all
payments on his own account to be made; and he makes them to pass
current universally over all his kingdoms and provinces and
territories, and whithersoever his power and sovereignty extends. And
nobody, however important he may think himself, dares to refuse them
on pain of death. And indeed everybody takes them readily, for
wheresoever a person may go throughout the Great Kaan’s dominions he
shall find these pieces of paper current, and shall be able to
transact all sales and purchases of goods by means of them just as
well as if they were coins of pure gold. And all the while they are so
light that ten bezants’ worth does not weigh one golden bezant.
Furthermore all merchants arriving from India or other countries, and
bringing with them gold or silver or gems and pearls, are prohibited
from selling to any one but the Emperor. He has twelve experts chosen
for this business, men of shrewdness and experience in such affairs;
these appraise the articles, and the Emperor then pays a liberal price
for them in those pieces of paper. The merchants accept his price
readily, for in the first place they would not get so good an one from
anybody else, and secondly they are paid without any delay.
-- The Travels of Marco Polo, Rustichello da Pisa, describing the 13th century empire of Kublai Khan.
There's some question whether a "Europe-esque medieval setting" could implement this as effectively as China did, but it certainly could make the attempt. I think one could argue that the "wonders" reported by Polo were as much an inspiration for the transition to the Renaissance as Classical western influences, but that's another essay ;-)
Note that there's a key balancing act here: the Emperor prints as much money as he likes and the money retains its value sufficiently well that an Indian merchant is prepared to sell his gold to the Emperor instead of taking it somewhere completely different. All artificial currencies have to play this game, and sometimes their controlling authorities get it wrong and the currency is debased.