Aspect-Oriented Programming is most definitely a programing paradigm. It is actually used all the time without people even realizing it. It can be done in any language kind of like the way you can use object-oriented programming in a language like C that doesn't have any direct support for it.
Most people only think of AspectJ when they hear about AOP, but that's just one popular language/implementation. AspectJ feels like an add-on because it simply adds more AOP features on top of an otherwise existing language. That says nothing for the paradigm itself.
AOP is all about separation of concerns. Encapsulation, modularization, and the ability to split blocks of code into functions -- some of the most fundamental concepts in programming -- are all a part of aspect-oriented programming. To do true AOP though, you go even further, and separate concerns at the statement level. Pointcuts are yet another feature designed to separate concerns when certain ones necessarily cut across -- or crosscut -- other abstractions.