I don’t believe for a second that there was actually a chance of Cheney being removed in 2004. People have allegedly “privately discussed” replacing every VP, but it never actually happens. The last time it was even a serious possibility (excluding the previously mentioned Agnew->Ford->Rockefeller->Dole shuffle 72-76) was Nixon in 56.
The only other possible example (and only instance in my 37 years) was there being speculation briefly that Dan Quayle might have been dropped in 1992 following the "Murphy Brown"/"potatoe" incidents. Even then, that rumor was quickly quashed (probably because it seemed that Bush 41 would have alienated more conservatives than he already had with the breaking of his pledge not to raise taxes).