Rust, 618 bytes (not competitive)

extern crate rand;fn main(){let t=("extern crate rand;fn main(){let t=", ";let s=format!(\"{}{:?}{}\",t.0,t,t.1).into_bytes();let l=[*s.last().unwrap(),0];let mut u:Vec<_>=s.windows(2).collect();u.push(&l);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!(\"{}\",c as char);c=rand::sample(&mut r,u.iter().filter(|x|x[0]==c),1)[0][1];}}");let s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();let l=[*s.last().unwrap(),0];let mut u:Vec<_>=s.windows(2).collect();u.push(&l);let mut r=rand::thread_rng();let mut c=s[0];while c!=0{print!("{}",c as char);c=rand::sample(&mut r,u.iter().filter(|x|x[0]==c),1)[0][1];}}

Since I already had written a pretty neat Rust quine for another question, I thought I'd adapt it for this, since it seemed simple enough. While the original was small, though, for this I have made very little attempt to minimize size. Here's an expanded version to explain what's going on:

-- Random numbers are removed from the standard library in Rust,
-- I had to make a cargo project to even compile this...
-- Rust is hardly a golfing language.
extern crate rand;

fn main(){

    -- The quine is fairly simple, we just make a tuple with 
    -- "everything before this tuple" as first element, and
    -- "everything after this tuple" with any quotes escaped 
    -- as second. That makes it really easy to print.
    let t=("[...before...]", "[...after...]");
    
    -- Instead of printing it, we save it as a byte vector
    let s=format!("{}{:?}{}",t.0,t,t.1).into_bytes();

    -- We slide a 2 wide window over it to save a vector
    -- of all bigrams. We append (the last character, 0)
    -- as a special bigram to mark the end.
    let l=[*s.last().unwrap(),0];
    let mut u:Vec<_>=s.windows(2).collect();
    u.push(&l);

    -- Start with the first character
    let mut c=s[0];
    let mut r=rand::thread_rng();

    while c!=0 {
        print!("{}",c as char);

        -- Filter the list of bigrams to only those which have the
        -- current character as first. Take one at random, its
        -- second is our next character.
        c=rand::sample(&mut r, u.iter().filter(|x|x[0]==c), 1)[0][1];

        -- Keep at it until the 0 byte is generated.
    }
}

Sample output 1:

eran(),0{ller=samarin chas c).pr,teteran mut madoletet manthilaplerng().wind_byt.wit();let.u.0][*s=[*s.plleas.wshit, rnd:Vec<_byte mputextet ut t leat=r,t rant!=r().filllet rng();lar("{}{let.ind_byt.what amusarando_ramut!=st ct!(\").0]=colet!(&lec<_ret.plec=s.whrararandormpr=saile ret=r,0]=r);le(\"),t und;fint.prilt!();ler(2).forap(&ler=s(),t ut rat mu:t=ramund:Ve s.putec==[0];wst and_byt sh(\"et c s[1), munwhras[0];c=s=s="etornws(2)[0, ain(|x|x[0,0,0];fowile c ct(&l=",tes().co_byt().wrmat ash(|x|x[*s.lethrant.wrarmu.file(\"et, r==[1);uterile().0,t ando_rinwhas=[0{}"ect.wilant!("{ple mut, mut mamprmant,0];le(&lec=s.1),t co_>=fin mamustec!(\",c=[0];}}",0];leteteat.ust(",ternwhashrarmut ler("erat,0]==file and_reter==s.utet an letet.ut=", ras.1);fin("{:?}"et t letes[*sado_bytet rnd::Verain s[0];whant(){}{}\"echin s(2);lerad;wst reth(\",t u.iletermat c 1];}{}

Sample output 2:

et!().0][0][0{}