Haskell, 143 137 bytes

This is probably way too long, but it works. (Thanks to @Lynn for the cartesian product trick!)

b%l=[x:l|x<-mapM id[[1>0,1<0]|_<-b],x/=b,1==sum[1|(a,b)<-x`zip`head l,a/=b],x`notElem`l]
b!a|f<-concat.((b%)<$>)=b:until(null.f)f[[a]]!!0

Try it online!

Explanation:

b%l -- given a path l (that should end in b) this generates all possible paths 
    -- that are one vertex longer than l and do not contain the same element 
    -- twice and do not contain b
            mapM id[[1>0,1<0]|_<-b] -- generate all possible vertices of the hypercube
             -- and check the criteria:
b%l=[x:l|   ...  x/=b,1==sum[1|(a,b)<-x`zip`head l,a/=b],x`notElem`l]
  
b!l -- begin with the vertex a and apply the function from above repeatedly
    -- to all remaining pathsuntil you cannot make the path any longer 
    -- without violating the criteria
   |f<-concat.((b%)<$>) -- define helper function 
                       =b:until(null.f)f[[a]]!!0 -- apply iteration until it stops, then
                                                 -- extract first element and prepend b