Luis Suarez gjorde fyra mål, medan Lionel Messi också hjälpte sig själv till en hatt-trick och Neymar missade ett straff.
Valencias sak blev inte hjälpt när försvararen Shkodran Mustafi skickades iväg för att smutskasta Messi i första halvan.
Neville är också utan en liga seger i åtta försök sedan ta över klubben i december.
Före detta England och Manchester United full-back Neville återvände till scenen av en av hans största triumfer.
Som 24-åring var han en del av United Team som vann Champions League med en spektakulär sen comeback mot Bayern München i 1999 års final på Nou Camp.
Den här gången skulle det inte bli någon mirakulös omsvängning.
Detta är testtider för 40-åringen som redan var under press innan matchen mot de europeiska mästarna.
Copa del Rey hade hittills erbjudit åtta-tidens Premier League vinnare Neville lite tröst efter fem dragningar och tre nederlag i La Liga.
Alla fyra av hans vinster från 14 spel som ansvarar i Spanien har kommit i denna tävling - men detta var inget annat än pinsamt.
Valencia var chockerande från början till slut och det skulle bara bli ett resultat när Barca gick 2-0 upp på 12 minuter.
Suarez bröt dödläget efter racing på Neymars pass innan den tidigare Liverpool spelaren fördubblade ledningen, curling hem från 10 meter efter en andfådd rörelse.
Messi avslutade ett härligt drag för att göra det 3-0 innan en frenetisk ände till hälften.
Argentinastjärnan nekades av baren och Neymar träffade posten från straffplatsen - efter att ha blivit befläckad av Mustafi, som skickades iväg.
Det gick från dåligt till värre i andra halvan, Suarez back-heel tillåter Messi att välja sin plats inne i området och ta sin karriär stämmer till 500 mål.
Hemskt försvar av Valencia tillät Messi att slutföra sin hatt-trick och göra det 5-0 efter att ha vunnit bollen tillbaka innan skjuta förbi innehavaren, som borde ha sparat.
Suarez hat-trick mål var en nära håll huvudet och det fanns fortfarande tid för Uruguay International att få sin fjärde - och Barcas sjunde - som han hittade nätet via nära inlägget.
Återlämningsbenet äger rum på Mestalla nästa onsdag.
Så illa som Valencia var, Barcelona producerade en utställning av utsökt fotboll, en masterclass i avslutning.
Luis Enriques namn sjöngs av hemmafansen som börjar tro att deras lag kan avsluta säsongen med fem troféer.
Efter att redan ha förseglat Uefa Super Club och Fifa Club World Cup, är de tre poäng klara på toppen av La Liga med ett spel i handen. De möter också Arsenal i de sista 16 i Champions League.
Barca är i fantastisk form i rätt skede av säsongen, sveper undan alla före dem. De ser ostoppbara ut.
Det är kanske lika bra att Valencia inte är hemma på söndag - Nevilles team reser för att möta Real Betis i La Liga på söndag. Barcelona är borta på botten klubben Levante på samma dag.
Gary Nevilles Valencia led ett förödmjukande nederlag eftersom de krossades av Barcelona i Copa del Rey semifinal första benet på Nou Camp.