How to relay Wifi on Android device and add VPN to it?

[hap2001]

I've been bothered by this problem for so long...
So I have to use a VPN service that can only provide Android APP, and I want to share it to other devices running Linux.
Currently I'm using a proxy APP on cellular data, but it have many limitations.
What I really want is, let a phone/tablet connect to an existing AP, add VPN to it, and act as another AP, so any devices connect to the new hotspot are tunneled.
I've searched a lot but still not getting a solid answer, all I know is this at least requires a rooted device.
Is the whole thing even possible? What APPs should I use?

[JDubU]

I have zero personal experience with this, but it seems like you're describing an Android proxy server:

https://play.google.com/store/apps/details?id=cn.adonet.proxyevery&hl=en_US
https://play.google.com/store/apps/details?id=cn.adonet.proxy.server.pro&hl=en_US