Мобильное приложение (Android) и сайт. Как?
начните с API
А нужно ли? Если делать приложение, то нельзя "обижать" пользователей той или иной мобильной ОС. Значит, нужно будет делать минимум 3 приложения: под iOS, Android, WindowsPhone. Если все таки нужно именно приложение, то можно сначала запустить сайт, но сделать мобильную версию или ограничиться адаптивным дизайном. А уже потом спокойно заниматься API и приложениями. 
У Вконтакте тоже не сразу приложение появилось. Помню, пользовался мобильной версией, которая, кстати говоря, была и остается более функциональной, чем приложение (для WinPhone). Еще плюс - можно в любой момент переключиться на полную версию сайта.