Should I start searching now or wait until I get my Network+? I have my A+ right now, but I'm probably not going to get my Network+ until 3 months later. I have 3 months on the job here so far, I'm 20 years old and get paid $55k/year.
Counterpoint - almost all jobs will have elements of this type of stressful fuckery. Use it as a learning experience, and do your best to navigate the constraints while maintaining professionalism and value to your employer.
It's a balance; if it's truly soul destroying then your health and happiness is more important, get out. However, the more you learn how to deal with this, the less likely you are to burn out in other jobs when they get shit like this. Not so that you can just suck it up and grind away for awful bosses, but so that you can give yourself the maximum options for you, and stress less while going through it.
You already seem to have the right mindset about trying to do this right, so the one thing I'll say is this: everything in writing, straight away. It's easy to get too relaxed about this when it's all going smoothly, but then something catches you out and it's too late (eg already been told not to bring it up again).
This part will feel awkward, but to protect yourself, you need to send your boss an email summarising your conversation and your understanding of the outcome (not updating). Frame it as a "I hear you, and I apologise for my previous insistence" if it helps smooth things over, but just make sure it outlines your previous queries and suggestions and their response to you. It's the only way to cover your own butt in these situations, and it's a great habit to get into after every conversation that has decisions or changes etc. Put it in writing as a summary: you can refer back to it later and it let's the other person know you understood their position / instruction
See what you can get by putting some subtle feelers out. Talk to a recruiter or two. Best time to search for a job is while you have one, but you don't have to commit to it full time unless shit really hits the fan. You're more likely to get written up than fired initially anyway if he's not the owner, erratic or not he has to answer for that.
Continue working towards whatever certifications you want in the meantime, especially if the job pays/reimburses you for it.
Start looking now. Tell prospective employers that you're working on the certification and include it in your CV (as a work in progress, ofc). Job searches take a long time, and the sooner you start, the sooner you're out.
Edit: @[email protected] has exactly the correct approach for getting it in writing. Keep it professional, emotionless, as close to an accurate summary of the situation and the decisions made as possible.