TLDR: In all cases, the student definitely should be one of the authors. In most cases, I would argue for them to be the first author, but if the work required significant extension prior to publication it becomes a gray area. First authorship also obviously wouldn't apply if there is a field-specific policy on author order (e.g. alphabetically).
You should not deprive people of authorship because they did not write the paper - I think you misunderstood the ICMJE criteria on this point. To quote:
The criteria are not intended for use as a means to disqualify colleagues from authorship who otherwise meet authorship criteria by denying them the opportunity to [write/revise the paper or approve its final version].
You should ask the students to read and approve the paper thus enabling them to fulfill the criteria. I think almost all students will agree to do this as it is not a lot of work.
Personally, I prefer giving students first authorship. The most important argument is that there is a huge power differential in favor of the advisor. The student is usually unsure of the academic conventions and will likely accept whatever the advisor says (if only to make his life easier). Making them the first author ensures, that the student will not feel that someone unjustly benefited from their work - and at least in terms of time spent their contribution is usually several times larger than advisor's.
I actually turned my MSc. thesis into a paper. I had no clue on how authors should be ordered, so in the first draft, I put myself as a third author of the paper (my advisor and my consultant from another department came before me). As no one had any comment, I kept it that way and in retrospect, I feel a little regret about it. From anecdotal evidence (including a few questions here: AA, BB) I think I am not alone.
I have recently co-authored a paper in computer science (currently under review) with my BSc. student. The student has written the software, designed and performed evaluation of the software with human subjects and performed analysis - all after relatively heavy consultations with me. I have written the text of the paper (reusing literature research from the BSc thesis), extended the evaluation and re-analysed the complete dataset. I gave the student first authorship, although the student was initially reluctant (claiming that I had written the paper and brought in ideas) and I am very happy about the decision, as I think it encouraged the student to think of himself as a scientist, although he does not want to pursue academic career.