For example proving 2^n < n!, 4 is the 'base' that works for this exercise, then starting from there we prove p + 1 considering p has to be at least 4 and we have our result. However, I believe determining the first valid value without a previous proof is kind of odd.
The question is, how?
I don't want to upload my homework with assumptions justified like "it's obvious just try using 0,1,2,3 and see that it doesn't work".
A valid base case would be any case for which the statement is true. You usually find this by just plugging in numbers until you find something that works.
Something to keep in mind is that in real life you don't usually know that the statement is true ahead of time. Generally you have many specific examples worked out in some problem you are working on and you notice a pattern. Suspecting that the pattern may be true you try out a quick induction proof. Any of the results you already found which suggested the "fact" in the first place would be an appropriate base.
The base case is usually so trivial that it is either obvious or can be immediately calculated without difficulty. However, in a case such as yours where the first values do not work, one would usually proceed to show that there are a finite number of cases where the relation is not true, and then proceed to perform induction on the first (few) cases that do work.
For instance, in number theory the primes 2 and 3 are often exceptions to a relationship (because one is the only even prime, and they are the only consecutive primes), so $p \ge 5$ or $p \gt 5$ are common caveats.
The base of induction is the lowest element satisfying the criteria that you are proving, the least element in the set of naturals for which your property is assumed to hold. Perhaps it would be useful to give you a more beefy idea of induction aside from the usual "Base, Hypothesis, Inductive Step" method you were most likely taught.
For induction, we utilize a set of axioms for $\mathbb{N}$. Among these axioms are: $0 \in \mathbb{N}$, $\forall \text{ nonzero } n \in \mathbb{N} \text{ there exists a successor } s(n) \text{ of the form } n+1$, and that $0$ is no number's successor.
Now, when we prove something by induction, what we are doing is assuming that there is some set $S \subseteq \mathbb{N}$ of natural numbers satisfying some property, showing that the set is non-empty (showing for a base), and showing that if some arbitrary natural is in the set, its successor is also in the set. If we manage to do this, we effectively show that:
$S = \mathbb{N}- \text{the elements not in our problem domain}.$
You may comfortably intuit why this is true! If we have shown that for any element in $S$ that its successor is also in $S$, then we have shown that for our base $b \in S$: $s(b) \in S, s(s(b)) \in S, \text{ and so on.}$ Think of it like the domino effect knocking its way down the naturals.
Now we shall consider your example $2^n < n!, \forall n \ge 4$. Remember that our base is the least element of the problem domain $n \ge 4$, hence 4. So, let $S = \{ n \in \mathbb{N} | 2^n < n!\}$. To show that $S$ is not empty, we explicitly show it for our base: $2^4 = 16 < 4! = 24$ hence $4 \in S$. Now we will assume that there is some $k \in S$ meaning that $k$ satisfies our desired property $2^k < k!$. To show that $s(k) \in S$ we do the usual manipulations of induction, which I'm sure you've already done for this problem, and show $2^{k+1} < (k+1)!$ and hence $(k+1) \in S$.
SUMMARY I really hope this helps with induction. If it confused things, then ditch the ramble and just know that the basis is the least element of the given problem domain, which is usually given to you (in this case $\forall p \ge 4$).
