Edit Mesh=Chamfer vertex. By your description this would be the most straight forward tool however be prepared for mixed results. The more edges you have per vert and the rounder you want the result to be the more unwieldy your model will get. Use with caution.
NOTE: this tool, like bevel, is UV destructive. It will create a void in your UVs when you use it. You will have to re-project the new faces to fit them back into your UV maps as well as do edge flow touch ups. This tool only creates parameter edges connecting the new verts so if you click recklessly you could easily end up with a 35 sided polygon.