Sharepoint - Is it possible to develop a Provider hosted app for SharePoint Foundation?

Provider hosted apps supported for SharePoint Foundation. Take a look here
For building provider hosted app you don't need Azure or User profile service. For on-premise you can host your app anywhere you want (except SharePoint servers).

In high trust scenario your app will produce OAuth access tokens by using certificate. The only things needed for high trust are apps configured correctly and domain users.

UPD
In short, yes, it's possible to create provider hosted app for SP Foundation (no User Profile Service required).
Just to prove my point here the screencast video I've just created - http://www.screencast.com/t/53rrlwTy10T

Ok, the long answer

In high trust scenario the app itself produces OAuth token (that's why it's called high trust - the app is so trusted, that SharePoint also trusts to access tokens, generated by the app).

If you need to have an access to SharePoint resources via CSOM, you need to be authenticated inside SharePoint. This is possible via S2S OAuth flow (for online this is also OAuth, but with help of ACS). So you need OAuth access token. You can acquire it with helpful classes like TokenHelper.cs and SharePointContext.cs.

How does TokenHelper.cs work in case of high trust? It simply grabs user SID (unique domain security identifier), attaches it to list of claims and later generates access token. Two points are important here - your app generates access token and user SID is attached into the resulting access token (encoded).

Here are screenshots from TokenHelper when generating access token:

Then we attach this access token to request and we are good to go (authenticated). You see, in order to be authenticated in SharePoint, only user SID is required. You can grab it using many different way - with ADFS auth (ADFS sends SID claim), you can call .net method and get user SID by user name - NTAccount f = new NTAccount("username");SecurityIdentifier s = (SecurityIdentifier) f.Translate(typeof(SecurityIdentifier));String sidString = s.ToString();

All this auth options described here - Plan for app authentication in SharePoint 2013, part "Choose user authentication methods for on-premises apps"
Now we know how user gets authenticated in SharePoint.

What about this part - "Address User Profile application service considerations" here:

High-trust apps generate their own access tokens, which include an assertion of the identity of the user on whose behalf they are acting

assertion of the identity of the user - that's our SID from screens above.
Did you see in SharePoint, when an item was created by the app, the created by is actually "created by <App Name> on behalf of <User Name>":

In order to extract this <User Name> SharePoint inspect incoming access token and extract user name. This process called rehydrating the user’s identity. Do you remember, we put SID right inside our access token. So the SharePoint can easily rehydrate the user by SID.
From the article you can also see, that not only SID can be used, but also AD DS UPN, SMTP name, SIP.

For SharePoint Enterprise, User Profile service is responsible for this process, that's why it's important to have it running. SharePoint Foundation also rehydrates user identity, but since there is no user profile, it uses other services for that purpose (I guess App Mng service). But that doesn't mean, that User Profile Service is required to make the app work in Foundation. In Foundation other services is responsible for rehydration.

UPD2
As I said, I did the project in the past without issues.

Now why I downvoted -
High-trust apps will need user profiles service app - that's wrong, no user profile required, you can see the prove from my screencast above.

You can do the development, but it's going to be limited, once you start doing the authentication part - that's wrong, as I explained in my update, authentication is related to your app and can implemented in many various ways (and msdn article also proves that), it doesn't require user profile service at all, because your app authentication doesn't interfere with SharePoint services.

and these limitations are regarding user profiles, which are needed for identity verification - that's wrong, because like you just said Foundation uses Users List for rehydration.

that doesn't mean it's the way to go to recommend it to someone - where do you see I recommend something? I'm saying it's possible from my practice. All this assumptions about User Profile service is totally wrong. Also, just points to think - why does MS include developer site template for Foundation? Why there is a section "Apps: in Foundation under central admin?

people out there are having issues when doing it on Foundation do you know exact reason why the user getting 401? It doesn't mean that becasue of Foundation.

High-trust apps will need user profiles service app, which is not available in SharePoint foundation.

Here's a similar case:

https://social.msdn.microsoft.com/Forums/office/en-US/4fdee1a9-1493-4cd9-8166-4c90c27866c0/developing-provider-hosted-apps-in-sharepoint-foundation-2013?forum=appsforsharepoint

Planning for authentication:

https://technet.microsoft.com/en-ca/library/jj219806.aspx