Mike, as many have said, make a template (paper, etc)- and we all know you thought of that.
I would make the template, leaving everything in place, transfer it to a piece of 1/4" ply and shape it to fit.

THEN remove the existing board, cut the new board to rough shape, template rout to final shape and install.