G,
Is network security something that could possibly be self taught and get a job in (like programming can be) or no?
Depends on what you mean by the term Network Security. Are you meaning something in the realm of merely hardening devices (port security, dot1x, ACLs, firewall modification, etc.), like a network or boundary protection team might do/use? Or do you mean something more like ArcSight, Snort, Nessus, etc. which are more likely to be used by a Security team?
If the former, yes. However, unless you already have experience in it from your days in the Navy you will not be likely to start out doing that actual work. You'd either have to start as a Jr. Network analyst/engineer (depending on the position title at the company) or maybe even lower (desktop support or even service desk). It really depends on the company. Part of the problem once you get into stuff like CCNA Security is it uses software which is not able to be used in PacketTracer -- stuff like ACS, ASDM on the ASA, etc. You can access those images through Cisco's learning platform, but it's not free or even particularly cheap. There is an alternative: Juniper. They don't have quite the marketshare of Cisco but they do have a marketshare. They're also kicking Cisco's butt in certain spheres. They make available their images for free, as they want people to learn their stuff and thus increase the value of their brand to the market. I believe Palo Alto's images are also available for GNS3. Cisco images for GNS3 are hard to come by legally. But you could focus on Juniper certs. The concepts are pretty much the same, just the syntax and phrasing of the commands differ. Build up a cool home lab in GNS3 w/ Juniper and you could definitely do some cool self-training. Add in some VMs of Kali Linux, basic Windows and a few others and you could practice both networking and CEH pentesting concepts.
I just did a search on eurojobs.com for both "Juniper" (85 results) and "Cisco" (87 results) and "CCNA" (22 results). So the job market for either isn't awful. You can play around with the free Cisco emulators enough to get by on the majority of that sort of work.
As for the latter, that will be harder. Those sorts of tools are often pay to play or at least pay to access features. I'm sure if you dig around you can find ways to at least get a handle on the software. It's not yet my field -- I'm still putting in my time w/ the network-specific side of the house. The other problem is those tools need something to scan. In other words, you need to know how to set up a network at an appreciable level for them to be of actual use for studying.
Keep in mind, all information is truly self-taught and I'd classify your use of self-taught more as self-driven. The difference is your resource(s) for gaining the knowledge. For many people, that involves actual classes, instructors, boot camps (condensed classes -- best for people with familiarity who just need a crash course refresh), etc. Some are able to cobble it together on their own. Sometimes self-driven is not the way to go due to lack of access to the product itself -- often provided as part of the tuition for classes and boot camps. Most instructors merely facilitate a guided tour of a book, or otherwise rip off a book for their class material. With YouTube, Reddit, etc., there's no real need for an instructor these days imo.
For CCENT/CCNA R&S/CCNA Sec, the best single test prep resource I've found is Boson. Boson has net sims and labs for CCENT and CCNA as well as test engines which are very accurate and comprehensive. For CCNA Sec they have a test sim, which is fairly on point and includes sims needed for the current version. Caveat: CCNA Sec is very broad AND deep in its questions (some are very simple, but others require a knowledge level CCENT and CCNA R&S did not) and requires multiple resources. As one CCNP level engineer at work put it, "I'd rather take CCNP all over again than ever take CCNA Sec again". It's a rough one.
I haven't touched A+, Net+, or Sec+ in 3 years. They all renewed due to Linux+ and CCNA Sec. I'm unsure of the best way to go for those.
I wouldn't recommend Net+ if one intends to go for Cisco. That knowledge is covered in CCENT. A+ would help w/ getting an entry level job, at least in the US. Unsure about EU or CAN. Linux+ was rough, mainly because it was so pedantic and largely full of useless info. I'd focus more on RedHat certification for anything Linux specific. It's actually recognized as needed in that world.