I don't like to see questions on the forum left unanswered, particularly when they are from newer users, so although I am not an expert on this topic I will try to tell you why your question has not had a response after nearly 24 hours.
Your question has been asked many, many times before. Essentially you are asking "How can I identify a specific device?". The answer most often given is to use the advertising id. This is the answer that Google appears to recommend
here. But the advertising id can be changed. I don't know how to do that, but if I thought that it would save me money then I am sure that I could find out. If you want to try that path then here is
a link.
Another identifier that is often mentioned is the MAC number. This might work in many cases but is not a watertight guarantee as it can change, and I am not sure if it is always accessible. Depending on your app it might be good enough. Search the forum and you will find out more but ignore older posts - things have changed.
In any case search the forum for "unique id" and similar terms - there are dozens of posts.
You ask specifically if it is possible "to leave a marker on the device". The answer is "Yes - you could write a marker file", but with recent Android versions you need the user's permission, so they know where the marker is stored and would be able to remove it (using a file manager app or by connecting to a PC). Again, not every user will know how to so this, so it will work sometimes.
The only way that I think a server-less registration system could work would be if your app generates as asset that the user would lose when they re-install. So a fitness app would lose your step-counter history, for example, or a game app would lose your high-score table.