I've ended up with concatenating each of my model and ViewModel classes with EntityState property, so now when I change some property I set the EntityState to changed state, when I create one I set the property to state Added, initially models are initialised with Unchanged state, basically it looks something like the following:
[Table("City")]
[KnownType(typeof(Country))]
public class City
{
    public City()
    {
        Airports = new List<Airport>();
        LastUpdate = DateTime.Now;
    }
    [Key]
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public Int32 Id { get; set; }
    public Int32? CountryId { get; set; }
    [StringLength(50)]
    public String Name { get; set; }
    [Range(-12, 13)]
    public Int32? TimeZone { get; set; }
    public Boolean? SummerTime { get; set; }
    public DateTime? LastUpdate { get; set; }
    [ForeignKey("CountryId")]
    public virtual Country Country { get; set; }
    [NotMapped]
    public EntityState? EntityState { get; set; } // <----------- Here it is
}
Then on server I do the following 
    [HttpPost, HttpGet]
    public HttpResponseMessage SaveRecord(RecordViewModel record)
    {
        var model = Mapper.Map<Record>(record);
        if (!ModelState.IsValid)
        {
            return Request.CreateErrorResponse(HttpStatusCode.BadRequest, ModelState);
        }
        db.Attach(model);
        try
        {
            db.SaveChanges();
        }
        catch (DbUpdateConcurrencyException ex)
        {
            return Request.CreateErrorResponse(HttpStatusCode.NotFound, ex);
        }
        return Request.CreateResponse(HttpStatusCode.OK);
    }
Here is implementation for Attach method:
    public void Attach(City entity)
    {
        if (entity != null)
        {
            Attach(entity.Country);
            AttachAndMarkAs(entity, entity.EntityState ?? EntityState.Added, instance => instance.Id);
        }
    }
    public void Attach(Country entity)
    {
        if (entity != null)
        {
            AttachAndMarkAs(entity, entity.EntityState ?? EntityState.Added, instance => instance.Id);
        }
    }
AttachAndMarkAs has the following implementation:
    public void AttachAndMarkAs<T>(T entity, EntityState state, Func<T, object> id) where T : class
    {
        var entry = Entry(entity);
        if (entry.State == EntityState.Detached)
        {
            var set = Set<T>();
            T attachedEntity = set.Find(id(entity));
            if (attachedEntity != null)
            {
                var attachedEntry = Entry(attachedEntity);
                attachedEntry.CurrentValues.SetValues(entity);
            }
            else
            {
                entry.State = state;
            }
        }
    }