You could modify the existing Bitcoin client to do that. Call it 'Creditcoin'.
An amount of creditcoin would not be just a number as in Bitcoin, it would be a tuple of a number plus the original address that issued it.
The owner of an address (owner of private key) would be allowed to send an unlimited amount out letting it's own balance go into the negative (thus everyone would also known how much of that creditcoin has been issued).
For example I own the address CL41Guib8ToDmWTHkxgVKtu8rBe4fv1foz and it could hold:
(1.23 ; C94a6sy4yci6hRrtczNG8kyvudEc5bza2W)
(0.56 ; C8P5oMR3P7okPsRiuVEp7S3PfdMV2EFwe)
(234234.421234 ; CEHT891iWJyKzQDdLrtTG271yhTH7XDqBm)
(-500; CL41Guib8ToDmWTHkxgVKtu8rBe4fv1foz) <=== this means I have issued 500 CC
Note: I'm not sure what kind of incentive you could have for miners though. Maybe issue a coin inside the network with the address '0', which would then function like the normal Bitcoin.