You can do this, but wait until fall. You don't want to plant a shrub in hot weather.
Getting the shrub and all its roots out will be the tough part.
Cut back as much as you can now to make it more manageable.
Also, if it is very dry or compacted, water the area regularly to help removal.
Replanitng is the easy part, getting it out takes muscle.
What shrub is this, btw and why is it dying? This will help you in choosing your next plant.