There are certainly different ways to approach the problem, I am giving you what I think.
The main key is to create as many as features as you can, well it depends on what algorithm you may end up using, but still more features won't hurt. After all you want to differentiate each user, so your feature space should be rich enough to be able to distinct them from each other. I think you are on the right track. For example, there are many features can be extracted from date (weekday, weekend, month etc.), or the browser you mentioned, if it is multiple browser you can create a new feature num_broswers (count number of distinct browser that user uses). You better know your data. Are sessions equally spaced on time or not? For instance, could be that user_one exits a session faster than user_two? Then total time spent for each user on each session could be another feature (engagement factor). You mentioned time in your columns, but I would not know what it is. You can even take time_of_day as another feature (morning, mid-day, afternoon, evening etc.).
You need also to clarify in your question whether number of users are fixed for a specific period of time, or constantly changing?
After addressing key points about data and features, I am thinking of two algorithmic approaches:
This is exactly what you mentioned, and it is a valid approach and perhaps the fastest and most straightforward one. As mentioned above, you can make new features like num_browsers for multiple browsers entries for a user in those 40 sessions, which was your major concern. I am more concerned that naturally you may have a mix of numerical and categorical features, and I would not be very sure if normal KNN (Euclidean metric) would work! Doesn't hurt trying though after encoding those categorical features or normalizing features are not continuous, but check this post, or another one, or at least be aware of pitfalls!!
You could even turn this into a Multiclass Classification problem, i.e. classifying which user the new incoming user is based on features. The challenge is that the quality of your classifier strongly depends on your feature space. The choice of the algorithms does not matter (even kNN again can be used, but perhaps Decision Trees i.e. RandomForest would be better). If you won't have a good set of distinctive features, classifier can not do magic! This could be also true about kNN, but since kNN doesn't need training, you may get more reasonable results than a classifier.
P.S. This method would be more suitable "if number of users are fixed". Still it would be possible to train a classifier if number of users are NOT fixed. It is ONLY then you need to re-train whenever you have a new user or user_ids are changing, otherwise your algorithm have not seen such user and likely it is going to miss it!
I would personally go with the Similarity-based Method and try to enhance my features as much as I can.