So how hard would it be to walk on with a varsity sport at navy? I understand this would vary a great deal from sport to sport, but in general would they allow someone to walk on even if they weren't all-conference or something in high school? Can one practice with a varsity team if there is no club or intramural for that sport?
Navy is Division I in athletics, so the short answer is that it can be very difficult, depending on the sport, to "walk on." For a sport with a small roster, for example, like basketball, it is virtually impossible to walk on. Even in sports with bigger rosters, like lacrosse or football, it is difficult because Navy recruits aggressively. In lacrosse this year, a number of recruited plebes who had been at NAPS, did not make the team (although there was a coaching change/roster reduction).
And no, one cannot practice with a varsity team if you are not a member of that team, even if there is no club/intramural sport.
To get a sense of the qualifications of the athletes (all-Conference, All-State, other honors), you should check out the relevant Navy roster on navysports.com -- if you click on the names of athletes you'll get their bios. I think you'll see that their athletic "credentials" (awards/honors) are pretty uniformly impressive. Not surprising given that only a tiny fraction of high school varsity athletes go on to play at the Division I level.
There are some sports at Navy (e.g. certain club sports) more conducive to walking on, and you can ask around/get a sense of that as you explore the process more to see if those fit your skill set/interests. BUT club sports can be selective, and even varsity sports like men's rowing which traditionally had many "walk-ons" (new rowers), now significantly fill their roster with recruited and experienced high school rowers.
Don't give up, but do be realistic.