iPhone 4s: I keep receiving notifications over 3G for apps that I've disabled cell data for

Solution 1:

When you disable access for cellular data for specific apps like Pandora and YouTube, It only disables the access cellular data when you have the application open.

The push notifications you receive on your iPhone are sent through the Apple Push Notification Service (APNS). This is done so that the application does not need to run at the background to fetch new notifications all the time, Only the Apple's push notification service runs all the time checking for updates from all the applications.

All the more the push notifications uses a very minimal amount of data which won't be shown in the usage.