Yes, AES could be implemented on a 4-bit micro-controller such as this EM6626, and that would not be rocket science or stupidly slow. This application note illustrates that all kind of 8-bit operations are simple, and table lookups are possible.
In fact, tables are not even indispensable if performance is non-critical; see this minimalist AES source code in C which has a compilation option to avoid any table.
The most serious issue is the amount of RAM required: current 128-bit subkey and 128-bit data will eat half of the total 512-bit RAM of the above device.
Also worrying is the security: I know no 4-bit micro-controller with any kind of security evaluation. Thus I would trust such an implementation only if it is operated in a secure environment, and with a key that vanishes from the device after use. That's an appropriate security model for an enciphering machine, but not a copy-protection dongle.