After trying a bunch of suggestions I found via google I realized that I had made a bad assumption. Even though the ASP.NET Web Service is not an available project type when creating at .Net 4.5 project, you can create one. Basically you create one as a .Net 3.5 project and then change it to target the 4.5 framework. Or you can create a basic web site and just delete the .aspx pages and manually add .asmx pages. So. Basically I upgraded my web service to .Net Framework 4.5 and am now able to debug.
Note: I had a .Net 4.0 PC project created in VS 2010 that consumed a .Net 3.5 Web Service and was able to debug into it just fine. I was unable to get VS 2012 to do so. So that seems pretty shady. And was why I was so certain there was a way to debug across the .Net frameworks.
Anyway, this is the google result that helped me:
http://stackoverflow.com/questions/4345498/asp-net-web-service-application-missing-in-visual-studio-2010[
^]
Hope this helps if any one else has the same isssue.