If we look at the Dungeon Master’s Guide page 261, it has this to say:
You can do away with experience points entirely and control the rate of character advancement. Advance characters based on how many sessions they play, or when they accomplish significant story goals in the campaign. In either case, you tell the players when their characters gain a level.
This method of level advancement can be particularly helpful if your campaign doesn't include much
combat, or includes so much combat that tracking XP becomes tiresome.
As your players want to level up but do not want to track experience points, they are essentially describing this system. The DMG details two methods of levelling without using experience:
Session-based Advancement
A good rate of session-based advancement is to have characters reach 2nd level after the first session of play, 3rd level after another session, and 4th level after two more sessions. Then spend two or three sessions for each subsequent level. This rate mirrors the standard rate of advancement, assuming sessions are about four hours long.
Using this method, you can simply state that, after X amount of sessions, the players level up. This way allows you to get past the circular argument and simply state that “okay, its been enough time, you’ve levelled up”.
This may be a better method as, by levelling players up based on how many sessions they’ve been playing for, you allow for the game to flow easier. Your players no longer would need to feel they have to grind XP to be able to advance to the next stage, they would know that next session, they are guaranteed to level up. This may encourage them to do something else to advance the story as it is clear that nothing will allow them to advance, beyond waiting a week to play again. Rather than wasting several hours, your players may instead try to advance the story despite feeling under-levelled, simply because there would be nothing else for them to do for the next few hours if they did not try and advance the plot or find something else to do.
Personally, i wouldn’t recommend you use this method as it seems that you want them to move on as quickly as possible, not spend several sessions killing monsters to fulfil the required number of sessions to level. Instead, i would recommend using the method below:
Story-based Advancement
When you let the story of the campaign drive advancement, you award levels when adventurers accomplish significant goals in the campaign.
Whilst this explanation is very brief, it offers you the possibility of levelling up the players as the story demands it. Your players will not leave until they have gained a level, so simply give them a level. This allows you to progress and continue your story, rather than getting bogged down with the players grinding for experience points that don’t exist. For example, you could state that:
“after days of slaughtering the denizens of the forrest, your characters feel more experienced and confident that they can face more dangerous challenges - you have gained a level”.
To put this into movie terms, what you have done is described a training montage. Rather than showing every fight and acting it out, you have simply stated that “X has happened, now we’re at this point”. This is similar to a travel montage in how, rather than describing every hour in excruciating detail, potentially grinding the game to a halt, you have shortened the sequences down to keep to momentum and flow of the game going.
To prevent this from being abused, such as the players saying “do a montage until we reach level 20”, you could again use the story-based levelling system to your advantage. “After a while you find that the creatures no longer pose a threat to you and simply flee rather than attempting to fight - you do not level up”. There was no story-based reason for them to gain a level so they have not gained one, they did not try to earn it and wanted to instead skip to it.
Milestones
Whilst you mentioned milestones, I believe what you’ve actually described is Levelling Without Experience. My interpretation of Milestones is that they are like XP rewards for completing a quest objective. So, for example, by “obtaining the sword of Rafaam”, in whatever way you chose, be it through combat, social encounters or exploration, you have completed that objective and are rewarded with XP. This is as opposed to only gaining experience for killing monsters and no XP is granted for avoiding them or dealing with then in a non-combat way.
Using milestones, in the way I interpret the rules, players could gain a large chunk of experience for completing the objective “slay the monsters of the forrest to hone your skills”, allowing them to level up (or get closer to levelling up). This would help you to advance the story as players know they don’t need to always accomplish great feats in order to gain a level, smaller successes build up and eventually lead to gaining a level, though this is a much different style of gaining experience than what your players may be familiar with.
Your players may be more willing to accept this type of gaining experience as it focuses on the completion of objectives, which is what they seem to want, but it also allows you as the DM to give them smaller level-based rewards, rather than giving them an entire level each time and trying to come up with a plausible scenario or reason for them to gain a level.
Additionally, your players may be more familiar with this style of gaining experience as this is what many games employ. One example being The Witcher 3, when you complete a quest or a contract, you are given a large chunk of experience points. This rewards you for completing the objectives of a quest and seeing a quest line through to its completion.
My interpretation of milestones, detailed above, seems to be in the minority. It appears that most people interpret the rule to be very similar to Story-based Advancement - I however see the two as distinctly different methods. However, you could combine the two methods to create Story-Based Milestones:
Story-based Milestones
This method combines my interpretation of milestones with the idea of story-based levelling. Rather than gaining experience points at each milestone, players gain a tally mark. Minor milestones would only give 1 tally mark, major milestones might give 5 (or you as the DM might state how many tally marks a quest is worth). You might need, for example, 30 tally marks to get a new level, which is equivalent to 30 minor milestones or 6 major milestones.
A major milestone could be awarded for finishing a main quest objective, such as “slay the dragon”, “remove the archmage’s power”, “obtain the magical artefact” etc. A minor milestone might awarded for completing side quests or optional objectives or even completing main objectives using out-of-the-box thinking, for example “this cave entrance is littered with traps, the kobolds can’t possibly use this passage everyday, there must be another way in”.
This way, players might try and complete objectives which grant them many minor milestones, allowing them to get the “XP grinding” aspect they’re after, but it retains the idea of completing objectives to level up. Additionally, they might feel more compelled to complete main quest objectives as they allow them to level up faster, allowing them to get stronger which was their initial aim.