First of all, GL_QUADS are deprecated in OpenGL 3.3

Would having a spritesheet for each character mean too many vertex buffers?
No, you're going to run into texture memory problems before that would ever happen.
One of my friends suggested that in my spritesheet, I should make each sprite for the protagonist the size of his biggest frame.
In most circumstances that would be a waste of texture space / memory.
I feel like I can still keep a spritesheet or texture atlas with a bunch of unevenly sized sprites and still be able to access them without having to change the vertices of the VBO all the time. Is this possible?
Certainly, what you can do is create a static VBO for each spritesheet containing the vertices for the maximum number of instances you want to support for that sheet ( the sprites can simply be located at 0,0 and be 1,1 in size ). Provide the sheet data ( pixel coordinates ) to the vertex shader, pass the current frame for each sprite as a uniform, and render the visible amount by setting the count argument of glDrawArrays / glDrawElements. That way you never have to update your VBO's, don't have to re-allocate any memory, and keep the amount of data you have to upload to the GPU at a minimum.