Yes. It is possible to have an Android OS without anything remotely related to Google.
First approach would be to root your phone. Then next step would be to install a custom ROM which is by default free of Google like Cyanogenmod.
Head over to XDA and find the forums corresponding to your phone which will have necessary tutorials and possibly even built roms like Cyanogenmod like I mentioned above.
Now there would be two steps for installing a custom ROM such as Cyanogenmod/Paranoid etc.
First step is to flash the ROM via recovery. We will follow this step and flash the ROM zip.
Second step would be to flash GAPPS (short for Google Apps). This is the Google apps package (i.e Play Store and other Google services/framework etc). You can skip flashing this and you will have a phone which won't have any Google apps.
Of course, you will need a third party market to install apps. Some common examples of this are: Mobogenie, F-Droid, Amazon etc.
In case you decide not to install custom ROM for whatever reason, then your only choice would be to root and manually remove Google apps and framework using App Managers like Root Uninstaller.
Although I didn't quite get what you meant here:
take power from regular Linux distribution
If you mean install packages like we do in usual Linux, that won't work in Android. Yes, Android is Linux-based but only at core. The rest is Google's own proprietary code
smali. The apps run with Dalvik as VM which is a type of interpreter that executes files in Dex format. So although it's Linux at core, package installation and execution is somewhat different due to which you can't use Linux packages directly.