It's a little tricky to put into words, although I think that both of the ideas you mentioned there kinda capture aspects of it. I think if I was trying to illustrate it in a lesson, I would start by writing out the first four bars of the head and looking at what pitches the melody is playing on the 1 and 3. Start by playing a two-feel and just play those pitches. Then think about how this skeletal line is moving- like is the melody ascending or descending? Are they chord tones, and if so which ones? If the notes in the skeletal line sound weird as a bass line, think about why- are they passing tensions that are going to resolve on the next beat? Could you replace one of those pitches with another, perhaps with the root of the chord at that beat?
Once you've thought those things through and made some tasteful substitutions, switch to a four feel and stitch together the notes you selected. You can do it any way you wish, either using chord tones, melody tones, passing tones that just work well. There really is no rule, other than that it should sound good.
You can try other stuff too. For example, I think the most distinctive part of the head of Well You Needn't is the way the notes on beat 3 and 1 (I think its a D and an A natural in the first two bars) kind of pop in an ascending shape. Make a line that descends instead, being mindful about those two beats. etc etc
I guess if I had to sum it up I would say that you are trying to find a line that sounds like it is aware of the melody without necessarily restating or mimicking it, not afraid to play something that is counter to the melody (like descending when it ascends) but not so strongly that it distracts from the melody.
One of the reasons I advocate transcription so vehemently to my students is that improvising lines the way I'm describing requires that you have a mental inventory of known-good lines that you can draw from when you're doing this kind of exercise, and Monk could be pretty particular about what bassists played on his recordings, so I think studying those lines closely is kind of prerequisite for his tunes especially.
