Many answers given about the counting the number of necklaces and bracelets always refer to Burnside's Lemma or PET. It gives a relatively easy way to compute the number of ways with a formula. But I am wondering if there are other ways of doing this problem $\textit{without}$ using these theorems.
For example, how many necklaces are there if you have a prime number $p \geq 3$ of beads, and exactly 2 colors?
There are initially $2^p$ arrangements. If we consider necklaces, then for every multicolored coloring of a necklace, it is counted in total $p$ times, one time for every rotation. So it would make sense to divide by $p$ here to get rid of the overcount. The two monochromatic colorings of the necklace are only counted one time each, however, so we need to subtract those out of the total first. We have: $$\frac{p^2 - 2}{p} + 2$$ Adding back the two monochromatic arrangements at the end.
What do you think about counting bracelets now for the same problem? Does there exist a more intuitive way of counting like I have done above? Or do I not have a choice but go with Burnside?
You can indeed generalize the approach you took for prime length $p$ to composite length $n$. This requires you to apply inclusion–exclusion on the lattice of divisors of $n$, and the result is of course the same as the result from Burnside’s lemma.
I’ll work with an arbitrary number $k$ of colours to keep the results general.
For example, say $n=p_1p_2$ with $p_1$, $p_2$ prime. Then we have $k^n$ arrangements, of which $k^{p_1}$ have period $p_1$ and $k^{p_2}$ have period $p_2$. We also have $k^1$ arrangements with period $1$, i.e. $k$ monochromatic arrangements. By inclusion–exclusion, generalizing your way of counting for prime length, we have $k^n-k^{p_1}-k^{p_2}+k$ arrangements without period (i.e. period $n$), which form groups of $n$ rotationally equivalent arrangements, $k^{p_1}-k$ arrangements with minimal period $p_1$, which form groups of $p_1$, $k^{p_2}-k$ arrangements with minimal period $p_2$, which form groups of $p_2$, and $k^1$ arrangements with period $1$, which have no rotational equivalents. Thus the total count of $k$-ary bracelets of length $n=p_1p_2$ is
$$ \frac{k^n-k^{p_1}-k^{p_2}+k}n+\frac{k^{p_1}-k}{p_1}+\frac{k^{p_2}-k}{p_2}+k\;. $$
By comparison, Burnside’s lemma yields
$$ \frac1n\sum_{d\mid n}\phi(d)k^\frac nd=\frac1n\left(k^n+(p_1-1)k^{p_2}+(p_2-1)k^{p_1}+(p_1-1)(p_2-1)k\right)\;, $$
which is indeed the same count.
For general $n$ with arbitrary prime factorization, we need to apply inclusion–exclusion on the lattice of divisors of $n$, yielding
$$ \sum_{d\mid n}\frac1d\sum_{s\mid d}\mu\left(\frac ds\right)k^s\;, $$
where $\mu$ is the Möbius function. Now collect like powers of $k$ by exchanging the sums:
\begin{eqnarray} \sum_{d\mid n}\frac1d\sum_{s\mid d}\mu\left(\frac ds\right)k^s &=& \sum_{s\mid n}\sum_{d\mid n\atop s\mid d}\frac1d\mu\left(\frac ds\right)k^s \\ &=& \sum_{s\mid n}\sum_{r\mid\frac ns}\frac1{rs}\mu(r)k^s \\ &=& \sum_{s\mid n}\frac{k^s}s\sum_{r\mid\frac ns}\frac1r\mu(r) \\ &=& \sum_{s\mid n}\frac{k^s}s\cdot\frac sn\phi\left(\frac ns\right) \\ &=& \frac 1n\sum_{s\mid n}\phi\left(\frac ns\right)k^s\;, \end{eqnarray}
which is the result from Burnside’s lemma.