I remember out damaging the Royal Jelly with a 3* Nightblade in Dusker armor. I'll test it again tomorrow. Thinking back at when I was a 3* knight, I think I only did the starvation method once, and my allies could have probably handled it without starving him. Even before the Brandish charge rework I remember taking down the Royal Jelly with my 2* and 3* friends.
It's worth noting that the Royal Jelly actually has 3 phases. There is an audible crack and you'll see a crack on the Royal Jelly's crown to signify the second phase. The polyps respawn at the start of this second phase. I'm skeptical that the polyps respawn as fast as you seem to think (however, I will double check myself).
EDIT** Forgot bout this post! Anyways, I'm back from testing the Royal Jelly. What I found was this.
In short, yes you can still starve the Royal Jelly. However, upon triggering the second phase, the polyps respawn. They also will slowly respawn on their own, but this only seemed to happen in phase 2. I didn't try starving the final phase tho. In retrospect I probably should have.