We present the model of an ultrasensitive mid-infrared (mid-IR) photodetector operating in the mid-wavelength infrared (MWIR) and long-wavelength infrared (LWIR) domains consisting of a hybrid heterostructure made of nanopatterned graphene (NPG) and vanadium dioxide (VO$_2$) which exhibits a large responsivity of $Rsim 10^4$ V/W, a detectivity exceeding $D^*sim 10^{10}$ J, and a sensitivity in terms of noise-equivalent power $mathrm{NEP}sim 100$ fW/$sqrt{rm Hz}$ close to room temperature by taking advantage of the phase change of a thin VO$_2$ film. Our proposed photodetector can reach an absorption of nearly 100% in monolayer graphene due to localized surface plasmons (LSPs) around the patterned circular holes. The geometry of the nanopattern and an electrostatic gate potential can be used to tune the absorption peak in the mid-IR regime between 3 and 12 $mu$m. After the photon absorption by the NPG sheet and the resulting phase change of VO$_2$ from insulating to metallic phase the applied bias voltage $V_b$ triggers a current through the VO$_2$ sheet, which can be detected electronically in about 1 ms, shorter than the detection times of current VO$_2$ bolometers. Our envisioned mid-IR photodetector reaches detectivities of cryogenically cooled HgCdTe photodetectors and sensitivities larger than VO$_2$ microbolometers while operating close to room temperature.