How to prove NP-hardness from scratch?
The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem).  It is almost universally the case that a reduction is easier than a direct proof.  Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners.  There are lots and lots of problems known to be NP-complete; perhaps you can find one that is a more suitable partner than 3SAT.

Possibly useful: How do I construct reductions between problems to prove a problem is NP-complete?.