You just release a new version of the app at full price. Like Silvio Rizzi has been doing with Reeder for 5 major versions since 2010, pretty successfully.
As for "littering" Apple's app store, it's just rows in a database, of which there are millions. Waste sucks, but we're not talking about a meaningful amount here.